1996: two-year-old season

Air Express began his racing career in a maiden race over six furlongs at Yarmouth Racecourse on 5 June when he started at odds of 13/2 and finished second of the seven runners, beaten half a length by Quest Express. Despite his defeat he was stepped up to Group 3 class for his next three races: he finished third in the July Stakes at Newmarket, fourth in the Vintage Stakes at Goodwood and third in the Solario Stakes at Sandown. On 19 September the colt was dropped back in class for a minor event on good to firm ground at Yarmouth and recorded his first victory as he led from the start and won at odds of 5/4 by one and three quarter lengths from Grand Lad.^[5] The colt was tried over one mile in the Group 2 Royal Lodge Stakes at Ascot Racecourse ten days later and came home sixth behind the future Epsom Derby winner Benny the Dip. On his final run of the year, Air Express started the 50/1 outsider in an eight-runner field for the Group 1 Dewhurst Stakes over seven furlongs at Newmarket on 18 October. After looking outpaced approaching the final furlong he stayed on strongly in the closing stages and finished third, beaten a head and a neck by In Command and Musical Pursuit with Bahamian Bounty in fourth and Desert King in sixth.^[6]

1997: three-year-old season

On 17 April, Air Express began his second season in the Craven Stakes (a major trial race for the 2000 Guineas) at Newmarket in which he started at odds of 8/1 and finished fourth behind Desert Story, Grapeshot and Cape Cross. Although he bypassed the English 2000 Guineas Air Express won the equivalent races in two countries. Ten days after his defeat at Newmarket the colt was sent to Italy to contest the Premio Parioli over 1600 metres at Capannelle Racecourse in Rome. After recovering from a slow start, he launched a sustained challenge on the outside, took the lead in the final stride and won by a nose from Risiat.^[7] At Cologne in Germany on 19 May Air Express was one of thirteen runners for the Mehl Mulhens Rennen over 1600 metres. He was among the leaders from the start, went to the front 400 metres from the finish and came home one and a quarter lengths clear of Is Tirol, with the French-trained Fine Fellow half a length back in third place.^[8]

Although he was coming off two major wins, Air Express was made a 20/1 outsider when he returned to England for the St James's Palace Stakes at Royal Ascot in June. He belied his odds as he kept on well in the straight to take second place behind Starborough, with Daylami, Desert King and In Command finishing behind. In the Sussex Stakes at Goodwood on 30 July the colt was matched against older horses for the first time and made little impact, coming home seventh of the nine runners behind the four-year-old Ali-Royal. The French jockey Olivier Peslier took over from Doyle when Air Express started at odds of 9/1 for the Group 1 Queen Elizabeth II Stakes over one mile at Ascot on 27 September. Revoque started favourite, while the other seven runners included Entrepreneur, Bijou d'Inde, Rebecca Sharp, Allied Forces (Queen Anne Stakes) and Bahhare (Champagne Stakes). Peslier restrained the colt at the rear of the field before making rapid progress on the final turn and then switching left to make his challenge on the outside in the straight. He took the lead approaching the final furlong and held off the late challenge of Rebecca Sharp to win by a short head in a photo finish. The racecourse stewards asked Clive Brittain to account for the colt's improved performance but accepted the trainer's explanation that Air Express had been unsuited by the camber at Goodwood.^[9] After the race Brittain said "I knew this was a Group 1 horse, and if I hadn't given up betting when I started training, I would have lumped on... I thought Olivier gave him a dream of a ride. We thought his style would suit the little horse"^[10]

1998: four-year-old season

Air Express remained in training as a four-year-old but failed to reproduce his best form. At Newbury Racecourse on 16 May he started favourite for the Lockinge Stakes but never looked likely to win and came home seventh of the ten runners behind Cape Cross. A drop back in distance brought no improvement as he finished fourth of the five runners behind Donkey Engine in the Prix de la Porte Maillot over 1400 metres at Longchamp Racecourse on 21 June.