La MEA, fondée en 1945, a lancé ses premières routes aériennes entre Beyrouth et la Syrie, Chypre et l'Égypte puis vers l'Arabie saoudite, le Koweït et le Golfe. En 1963, suite à la fusion avec Air Liban, la MEA a ajouté des destinations vers l'Europe, le Moyen-Orient et l'Afrique de l'Ouest à son programme international.
En dépit de la fermeture de l'Aéroport international de Beyrouth pendant la guerre civile entre 1975 et 1990, la compagnie a pu survivre, en louant ses avions et le personnel à d'autres transporteurs internationaux.
Avec le retour à la normalité en 1990, la MEA a réussi à rétablir ses services vers ses destinations précédentes, à renforcer et améliorer son réseau vers l’Europe, le Moyen-Orient et le Golfe.
En 1998, un vaste programme de restructuration permit à la MEA de passer de la période des grosses pertes qui avaient atteint 87 millions de dollars en 1997 au stade des profits nets qui ont atteint 22 millions de dollars en 2003, et 50 millions de dollars en 2004. Le plan d’action inclut la révision du réseau, la rationalisation de la politique d'achats, la réduction des coûts, le lancement du programme Cedar Miles et des systèmes de gestion de la rentabilité, ainsi que d'autres mesures destinées à moderniser le réseau.
En été 2006, la guerre a fortement perturbé l'activité commerciale de la compagnie puisque l'aéroport de Beyrouth était fermé. MEA opérait alors des vols vers Damas mais clouait la majorité de ses appareils à Larnaca, Amman et Paris.
Toutefois, la crise fut de courte durée puisqu'une fois cette dernière terminée, l'activité de la Middle East reprit très rapidement.
En 2007, Middle East Airlines passa une commande auprès d'Airbus pour un nombre important de monocouloirs (famille des Airbus A320) mais aussi pour des Airbus A330.
