Icelandair har rødder tilbage til Flugfélag Aukureyrar, der blev etableret i 1937. I 1940 skiftede det navn til Flugfélag Íslands og fusionerede i 1973 med det andet islandske flyselskab, Loftleiðir: Icelandair (Flugleiðir indenrigs og Icelandair ude). Gradvist tog det engelske navn over.
Selskabet har gjort Keflavik til en international transitlufthavn mellem Europa og USA. De transatlantiske ruter tegner sig i dag for omkring halvdelen af selskabets flyvninger.
