Virgin Express started on 23 April 1996, when the Virgin Group (with chairman Richard Branson) bought the Belgian leisure airline EBA (EuroBelgian Airlines) and rebranded it into Virgin Express. It also took over EBA's fleet of Boeing 737s and operated this type of aircraft from thereon. The airline soon concentrated on low-budget scheduled flights out of its Brussels hub, and became a major competitor for Sabena and later SN Brussels Airlines. In October 2004, the Virgin Group sold its assets to SN Brussels Airlines, and both airlines were integrated into the parent holding company SN Airholding, chaired by Viscount Étienne Davignon. On 31 March 2006, SN Brussels Airlines and Virgin Express announced their fusion into a single company, named Brussels Airlines. The combined airline added long haul destinations and strengthened its position in Africa.
Three Boeing 737-300 (OO-VEX, OO-VEG and OO-VEH) were fitted with winglets (March 2007). All the aircraft of Virgin Express have now been painted in Brussels Airlines colours. The airline operated a maximum of 26 737 at its peak, and was given the first Joint Aviation Authorities air operator's certificate delivered by the Belgian Civil Aviation Authorities.
After the merger, all ten of the Virgin Express fleet went to Brussels Airlines. Brussels Airlines has since phased out its Boeing 737s.