1944 als Bedarfsfluggesellschaft in Island gegründet, hob sie anfangs nur für das auf der Insel stationierte Militär zu Rundflügen ab. Hierzu nutzte man zwei Stinson SR-8 und eine Avro Anson.
Ein Jahr später kamen zwei Noorduyn UC-64 Norseman hinzu, gefolgt von der ersten von insgesamt fünf Grumman G-21 Goose.
Zwischen 1947 und 1958 wurde der Flottenpark mit zwei Douglas DC-3 und sieben DC-4, sowie zwei Consolidated Catalina beträchtlich erweitert. Man übernahm Frachtdienste und Charteraufträge innerhalb des Landes und bemühte sich frühzeitig um den Erhalt von Verkehrsrechten in die USA.
1958 war es soweit und New York konnte ins Streckennetz aufgenommen werden. Während dieser Zeit nannte man sich Loftleidir Icelandic. Es zeigte sich jedoch, dass die Douglas DC-4 nur bedingt für diese Zwecke einsetzbar war und so wurden ab 1959 fünf DC-6 zur Unterstützung eingeflottet.
Natürlich band Loftleidir das europäische Festland ein und Luxemburg, Oslo, Stockholm, Frankfurt, London und Kopenhagen wurden regelmäßig bedient.
Um den Frachtcharter weiterhin wirtschaftlich betreiben zu können, wurden ab 1964 fünf Canadair CL-44 angeschafft.
Die gleichen wirtschaftlichen Überlegungen betrafen den Passagierverkehr und so führte man 1969 das erste Strahlflugzeug in Form der Douglas DC-8-55 ein. Mit Zukauf weiterer DC-8 in unterschiedlichen Versionen im darauffolgendem Jahrzehnt konnte man die alten Props aussondern.
Loftleidir war nicht die einzige international tätige Airline in Island und wirtschaftliche Überlegungen seitens der Regierung diese mit Flugfelag Islands zu fusionieren nahmen inzwischen Formen an.
Am 1.8.1973 wurde eine Holdinggesellschaft gegründet, worin beide Airlines zusammengefasst wurden. Trotzdem agierten sie weiterhin unter den bisherigen Marken.
Ein Jahr später wurden beide Gesellschaften endgültig unter den Namen Icelandair fusioniert.
2003 wurde die Holding gründlich umgestellt, so dass elf Tochtergesellschaften entstanden zu denen die Reise- und Tourismusbranche, Hotels, Frachtverkehr, der Groundservice und auch kurzzeitig der Name Lofteidir Icelandic auftauchte, welche mit Boeing B-757 und B-767 Urlaubscharter durchführte.