Virgin Express didirikan pada 23 April 1996, ketika Virgin Group (dengan ketua Richard Branson) membeli maskapai penerbangan rekreasi asal Belgia EBA - EuroBelgian Airlines, yang didirikan oleh Victor Hasson dan Georges Gutelman, dan mengganti namanya menjadi Virgin Express.[4] Mereka juga mengambil alih armada Boeing 737 EBA dan mengoperasikan pesawat jenis ini dari sana. Maskapai ini segera berkonsentrasi pada penerbangan terjadwal dengan biaya rendah dari hub Brussels, dan menjadi pesaing utama dari Sabena dan kemudian SN Brussels Airlines.
Pada bulan Oktober 2004, Virgin Group menjual asetnya kepada SN Brussels Airlines, dan kedua maskapai tersebut diintegrasikan ke dalam induk SN Airholding, yang diketuai oleh Viscount Étienne Davignon.
Pada tanggal 31 Maret 2006, SN Brussels Airlines dan Virgin Express mengumumkan penggabungan mereka menjadi satu perusahaan bernama Brussels Airlines. Maskapai gabungan tersebut kemudian menambahkan tujuan jarak jauh dan memperkuat posisinya di Afrika.[5]
Tiga pesawat Boeing 737-300 (OO-VEX, OO-VEG dan OO-VEH) dilengkapi dengan sayap (Maret 2007). Maskapai ini mengoperasikan maksimum 26737 pada puncaknya, dan diberikan sertifikat operator udara Otoritas Penerbangan Gabungan pertama yang disampaikan oleh Otoritas Penerbangan Sipil Belgia. Setelah merger, kesepuluh armada Virgin Express pergi ke Brussels Airlines. Maskapai ini telah menghapus Boeing 737-nya secara bertahap.
Virgin Express juga sebelumnya mengoperasikan pesawat berikut:[13]
