Icelandair is the cheapest airline available among several others to fly to Europe. It has earned the name as “Backpackers Airline,” and offering low cost flights to Luxembourg, Icelandair is now hard put to beat competitors on most routes it flies. The airline runs on New York/JFK, Newark, Sanford, Seattle, Toronto, Vancouver, Washington/Dulles and several more.