Alyemda se fundó en 1971, cuatro años después de la independencia de Yemen del Sur. Operaba una red de rutas en África y el Oriente Medio, con su base de operaciones en el Aeropuerto Internacional de Aden, llamado antiguamente RAF Khormaksar durante el dominio británico.^[3]​ La aerolínea empezó a operar con una flota compuesta por varios Douglas DC-6 y DC-3. A mediados de los 70s, Alyemda adquirió cinco Boeing 707 y un Boeing 720, y a principios de 1979, tres de Havilland Canada Dash 7 fueron pedidos directamente a la fábrica, llegarían en octubre de ese año. En 1983 Alyemda recibió su primer Boeing 737-200Adv, también a mediados de los 80s recibió dos Tupolev Tu-154 de las versiondes M y B2, donados por la Unión Soviética. En 1993 se uniría también a la flota de la compañía un Airbus A310 para rutas largas.

Después de la unificación de Yemen, la aerolínea fue renombrada como Alyemda Air Yemen en 1992, y nuevamente en 1995 como Alyemen Airlines of Yemen. El 11 de febrero de 1996, Alyemen fue fusionada con Yemenia Airways, dejando así una sola aerolínea nacional en Yemen.^[4]​

La aerolínea volaba a las siguientes ciudades en 1995:^[5]​

África

• Egipto: El Cairo
• Yibuti: Yibuti

Asia

• Catar: Doha
• Emiratos Árabes Unidos: Abu Dabi, Sharjah
• India: Bombay
• Yemen del Norte: Saná
• Yemen del Sur: Adén, Al Ghaydah, Al Mukalla, Ataq

A lo largo de su existencia, Alyemda operó las siguientes aeronaves:^[4]​

• 1 Airbus A310

• 1 Antonov An-26

• 1 Beechcraft King Air

• 5 Boeing 707

• 1 Boeing 720

• 2 Boeing 737-200

• 3 de Havilland Canada Dash 7

• 5 Douglas DC-6

• 2 Tupolev Tu-154

• El 22 de agosto de 1972, un DC-6 de Alyemda fue secuestrado por tres pasajeros mientras realizaba un vuelo entre Beirut, Líbano y El Cairo, Egipto. El acto fue descrito por uno de los secuestradores como un acto de reunificación de Yemen. El avión aterrizó en Nicosia, Chipre para recargar combustible y siguió hacia Bengasi, en Libia, donde los secuestradores se rindieron ante las autoridades. Ninguno de los 49 pasajeros y 6 tripulantes resultaron heridos.^[6]​

• El 16 o el 17 de septiembre de 1975, un DC-3 de Alyemda resultó con daños irreparables luego de un aterrizaje forzoso en el Aeropuerto de Beihan. El avión provenía de Aden.^[7]​

• El 1 de marzo de 1977, un C-47 se estrelló en el Mar Rojo poco después de despegar del Aeropuerto Internacional de Aden. Todos los 16 pasajeros y los 3 tripulantes murieron en el accidente.^[8]​

• El 26 de enero de 1982, cinco meses antes del inicio de la Guerra del Líbano de 1982, un Boeing 707 de Alyemda que transportaba armas desde Libia hacia Beirut, fue atacado por un avión de combate sin identificar. A pesar de que el avión sufrió graves daños, los pilotos lograron aterrizar a salvo en Damasco, Siria.^[9]​

• El 9 de mayo de 1982, un de Havilland Canada Dash 7 de Alyemda se estrelló en el mar mientras se aproximaba al Aeropuerto Internacional de Aden luego de un vuelo proveniente de Al Mukalla. De los 45 pasajeros, 21 murieron, además de dos de los 4 tripulantes.^[10]​

• El 20 de enero de 1983, un Boeing 707 de Alyemda fue secuestrado durante un vuelo entre Aden y Kuwait, el avión fue obligado a dirigirse al Aeropuerto Internacional de Yibuti-Ambouli, en Yibuti, Yibuti, donde los secuestradores se rindieron a las autoridades.^[11]​

• El 15 de agosto de 1985, un Boeing 707 de Alyemda que transportaba 65 pasajeros sufrió una pérdida de control temporal debido a un desperfecto del piloto automático y a un error del piloto. Los elevadores de la aeronave subía y bajaba sin control, lo que causó la muerte de dos pasajeros y una asistente de vuelo. Cuando los pilotos retomaron el control del avión desactivando el piloto automático, el avión realizó un aterrizaje de emergencia en Aden.^[12]​

• El 27 de agosto de 1993, un Boeing 737-200 de Alyemda fue secuestrado por un sujeto que demandaba que el avión se dirigiera a Kuwait u Omán. En vez de eso, los pilotos se dirigieron al Aeropuerto de Al Ghaydah, donde todos los pasajeros fueron evacuados y el avión fue asaltado por las autoridades.^[13]​

• El 14 de septiembre de 1994, un Boeing 737-200 de Alyemda sufrió un intento de secuestro mientras se dirigía de Aden a Sana.^[14]​

• Esta obra contiene una traducción total derivada de «Alyemda» de Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.