Yemenia will get you to where you need to go. It's also fun to say. You can try it now: "Yemenia Yemenia, Yemenia!" Now it's time for some background research. Yemenia Airways was founded in 1961 and flies to many destinations around the Middle East, Asia Europe, Europe and Africa.