Wie der Name schon verrät, wurde diese Gesellschaft in Birmingham gegründet. Die ursprüngliche Bezeichnung, im Jahre 1983, lautete Birmingham Executive Airways. Ein halbes Jahr später konnte man den Flugbetrieb aufnehmen und zum Einsatz kamen vorerst Jetstream 31.
Größeres Fluggerät folgte in Form der Saab-340 einhergehend mit Gulfstream 1. Als 1990 die ersten BAC 1-11 in Dienst gestellt wurden, hatte Maersk Air einen nicht unerheblichen Anteil daran, denn sie übernahm zu der Zeit Aktienanteile an Birmingham. Zu diesem Zeitpunkt änderte sich auch der Name in Birmingham European Airways und die Jets erhielten eine neue Bemalung.
Hier sollte zum Ausdruck gebracht werden, das das Streckennetz der Gesellschaft stark auf das europäische Festland ausgedehnt wurde.
Am 25.10.1992 fusionierte Birmingham European Airways mit Brymon Airways zur Brymon European Airways. Die Bemalung von Birmingham verschwand zwar vom Airlinerhimmel jedoch wurde die strikte Trennung beider Divisionen nicht vollzogen.