Als die erste Fluggesellschaft Südjemens, Aden Airways, am 30. Juni 1967 ihren Betrieb einstellte, wurde noch im selben Jahr die private Fluggesellschaft Brothers Air Services (BASCO) gegründet.[2] BASCO hatte zwei Douglas DC-3 betrieben. Nachdem sie im Jahr 1971 verstaatlicht worden war, wurde am 11. März 1971 Alyemda gegründet.[3]
Am 22. Mai 1990 vereinigten sich die beiden früher getrennten Staaten Nordjemen und die Demokratische Volksrepublik Jemen (vormals Südjemen) zu einem gemeinsamen Staat. In der Folge ging Alyemda am 15. Mai 1996 in der vormals nordjemenitischen Fluggesellschaft Yemenia mit Sitz in Sanaa auf.[4][5]
Am 1. März 1977 stürzte eine Douglas DC-3/C-47A-25-DK der Alyemda mit dem (7O-ABF) nach dem Start vom Flughafen Aden ins Meer. Die Maschine befand sich auf dem Flug nach Seiyun; alle 19 Insassen kamen ums Leben.[11]
Am 26. Januar 1982 wurde eine Boeing 707-348C der Alyemda (7O-ACJ) während eines Frachtfluges von Libyen zum Flughafen Damaskus von einem irakischen oder israelischen Kampfjet angegriffen. Das Flugzeug hatte Militärgüter geladen. Die irreparabel beschädigte Maschine konnte sicher in Damaskus landen. Personen kamen nicht zu Schaden.[12]
Am 9. Mai 1982 stürzte eine de Havilland Canada DHC-7 der Alyemda (7O-ACK) während des Landeanflugs auf den Flughafen Aden etwa 2 Kilometer vor der Landebahn ins Meer. Das Flugzeug war in Mukalla gestartet. Von den 49 Insassen wurden 23 getötet. Dies war der erste Totalverlust einer de Havilland Canada DHC-7.[13]