Rautatielinjan rakentaminen aloitettiin 1993 ja se valmistui 1998. Lokakuussa 1994 rakenteilla oleva tunneli romahti ennalta-arvaamattomasti, tuhoten toimistorakennuksen sekä pysäköintialueen. Romahdus pysäytti Lontoon metronJubilee-linjan rakentamisen, jonka rakennusurakoitsijat olivat käyttäneet samantyylistä tunnelitekniikkaa. Vuonna 1999 Heathrow Express -linjan ensisijainen rakennusurakoitsija Balfour Beatty tuomittiin onnettomuuden takia 1,2 miljoonan punnan sakkoihin.[1]
Heathrow Expressiä ylläpitää lentokenttäoperaattori BAA Ltd.:n tytäryhtiö, eikä se kuulu National Railin alaisuuteen, vaikkakin se käyttää sen raiteita.