The airport is located approximately 3 km (1.9 mi) west of the town of Keflavík, Reykjanesbær.

Originally, the airport was built by the United States military during World War II, as a replacement for a small British landing strip at Garður to the north.

In its first years the passenger terminal was mostly used for troop transport as well as transatlantic technical stops; civilian airlines Icelandair and Loftleiðir were still based at the smaller Reykjavík Airport.

[11] During the 1960s and 1970s, rallies were held to protest the U.S. military presence in Iceland (and in particular at Keflavík), and every year protesters walked the 50-kilometre (30 mi) road from Reykjavík to Keflavík and chanted "Ísland úr NATO, herinn burt" (literally: Iceland out of NATO, the military away).

[14][15] These new aircraft were considered too large for regular operation on the shorter runway at Reykjavík Airport and both airlines began operations of their new larger aircraft from the longer runway at Keflavík Airport, greatly increasing the civilian passenger traffic through the Keflavík terminal.

Subsequently, in April 1987 the Icelandic government finished construction of a relocated civilian terminal which was located on the north side of the airport.

[20] Due to its location, the airport is also an important diversion landing site for large aircraft in transatlantic ETOPS operations.

[21] The terminal was extended with the opening of the South Building in 2001, to comply with the requirements of the Schengen Agreement.

[23] The original Keflavík passenger terminal, built in 1949 and defunct since 1987, was demolished in 2018 to make way for new development on the airport site.

[25] As of 2023, proposals have not progressed past the planning phase but the route is safeguarded in local and airport masterplans.

[26] The airport was used as a hub by defunct airlines Iceland Express and WOW air until it ceased operations on 28 March 2019.

[28][29] Similarly, Icelandair moved all of their Greenland-bound flights, operated using De Havilland Canada Dash-8 turboprop aircraft, from Reykjavík to Keflavík Airport in 2022, to allow easier onward connections.

[30] In 2016-2019 and 2023, Icelandair operated a domestic service to Akureyri Airport, only available for international connecting passengers.

[35] A major expansion of the airport began in 2022, with an eastern wing being constructed east of the main terminal.

To access flights to non-Schengen countries (including the UK and United States), one must pass through passport control.