[7] At March 1975 YAC had 60 employees; the airline's fleet consisted of four DC-6Bs and four DC-3s that served domestic destinations and an international network that included Asmara, Cairo, Djibouti, Dhahran, Jeddah and Kuwait.

[7] In April 1978, a two-year contract for the provision of two Boeing 707-320Cs that included the supply of aircrews and engineering support was signed with British Midland Airways (BMA).

[12] The unilateral cancellation of the contract signed with BMA by Yemen Airways led the British carrier to file a claim against the Yemeni airline, which resulted in the impoundment of one of its Boeing 727-200s.

Domestic scheduled passenger services linked Sana'a with Baydhan, Hodeida, Mareb and Taiz; Abu Dhabi, Athens, Cairo, Damascus, Dhahran, Dubai, Jeddah, Karachi, Kuwait, Muscat, Rome and Sharjah were part of the international network.

The list of domestic destinations served at this time were Aden, Al Ghaydah, Ataq, Hodeidah, Riyan Mukalla, Sanaa, Seiyun, Socotra and Taiz, while Abu Dhabi, Addis Ababa, Amman, Asmara, Bahrain, Beirut, Cairo, Damascus, Dar es Salaam, Djibouti, Doha, Dubai, Frankfurt, Jeddah, Johannesburg, Karachi, Khartoum, London, Moroni, Mumbai, Nairobi, Paris, Riyadh, Rome and Sharjah comprised the international network.

[21] On 20 January 2010, then British Prime Minister Gordon Brown announced that, owing to concerns of terrorist activity in Yemen, flights between the UK and the country would be suspended, as long as the security situation would not improve.

[23] In March 2015, Yemenia was forced to suspend all flight operations until further notice due both to a military conflict that had Sanaʽa International Airport as a target of air raids and to restrictions over the Yemeni airspace.

[30][31] According to The National newspaper, in November 2018 Yemenia announced that they would be seeking to resume flights from Aden International Airport to Dubai, Abu Dhabi, Muscat and Salalah in the Persian Gulf and Asmara, Moroni, and Djibouti in Africa, as well as leasing more aircraft.

[38] On 17 June 2023, the first direct flight between Yemen and Saudi Arabia in nearly seven years has taken more than 270 Yemenis from rebel-held Sanaa to Jeddah, signaling easing tensions between the two countries.

The flight by Yemenia carried Yemeni Muslims embarking on the annual Islamic pilgrimage of Hajj in the Saudi city of Mecca.

[39] As of September 2022[update], Yemenia has an all-Airbus fleet that consists of the following aircraft:[50][better source needed] In 2008, during the Dubai Air Show, the carrier signed a contract for the purchase of ten Airbus A350-800s.