Euro Belgian Airlines wurde im November 1991 in Melsbroek, Belgien gegründet.
Hauptanteilseigner war die City Hotel Group. Mit Boeing B-737 begann am 1.4.1992 der Flugbetrieb vom Brüsseler Airport.
Die Gesellschaft wuchs schnell und man besaß in kurzer Zeit mehrere Boeing B-737 der Serie -300 und -400.
Das Streckennetz wurde kontinuierlich ausgebaut und neben den Hauptstrecken nach Faro und Palma de Mallorca kamen unter anderen Chania, Korfu, Girona, Glasgow, Edinburgh, Malta, Paris, Frankfurt /Main und Barcelona hinzu.
Im Charterverkehr deckte man München, Berlin, Düsseldorf und Paderborn ab.
Die Virgin Group unter Richard Branson sahen in Euro Belgian ein ideales Sprungbrett, um auf dem europäischen Festland ins Marktsegment einsteigen zu können.
Im April 1996 kam es zur Übernahme der Gesellschaft und zur Namensänderung in Virgin Express.