Durch die Unabhängigkeit des ehemaligen Protektorates Aden von Großbritannien und der gleichzeitigen Gründung der Volksrepublik Südjemen war der Weg frei für eine eigene Fluggesellschaft. Alyemda Democratic Yemen Airlines, so der Name, wurde daraufhin am 11.3.1971 in Aden gegründet.
Mit drei Douglas DC-3 und einer DC-6, die von der Vorläufergesellschaft BASCO übernommen wurden begann man den Flugbetrieb innerhalb des Landes. Als weitere DC-6 gekauft wurden eröffnete man die Strecke nach Tripolis.
Ab 1975 stieg man mit Boeing B-720 ins Jetzeitalter ein gefolgt von B-707 zwei Jahre später. Nun weitete man den Flugbetrieb auf Afrika und dem Nahen Osten aus.
Bis zum Ende der siebziger Jahre konnten die betagten DC-3 durch modernere DHC-7 ersetzt werden.
Weiterhin gelangte eine TU-154 auf VIP Flügen zum Einsatz und mit Eintreffen zweier Boeing B-737 konnten die DC-6 ausgesondert werden.
Der folgende Bürgerkrieg zwang Alyemda zur Stilllegung ihrer Aktivitäten.
Als am 22.1.1990 der Süden mit dem Norden Jemens vereint wurde, gab es zwar die ersten Pläne Alyemda mit Yemenia zu fusionieren, doch wurde dieses Vorhaben durch die ewigen Machtkämpfe im Lande vorerst vereitelt. Statt dessen erfolgte ab Januar 1992 die Umbenennung in Alyemda Air Yemen und ein Jahr später konnte man einen geleasten Airbus A-310 einsetzen.
Erst gegen Ende der neunziger Jahre standen erneut Gespräche auf den Plan die zum Ziel hatten beide Airlines im Lande zu vereinigen, da wirtschaftliche Gesichtspunkte eine wesentliche Rolle spielten.
Anfang 1997 war es dann soweit, Alyemda fusionierte mit Yemenia wobei der letztere Name beibehalten wurde.