The airport began as a military airfield built by the Imperial Japanese Army during World War II.

[7] After the war, the Department of Civil Aviation (DCA) of North Borneo, which later became part of Malaysia's Sabah state, took over the airport's operation and maintenance.

This marked the beginning of its transition from a military installation to a public airport, laying the foundation for future commercial air travel in the region.

Regular passenger services commenced in May 1949 with a weekly flight operated by Malayan Airways from Singapore, stopping at Kuching and Labuan.

[8] By 1950, the airport became a stopover point for biweekly flights between Hong Kong and Labuan, via Manila and Sandakan, operated by Cathay Pacific.

With increasing air traffic and the need to accommodate larger aircraft, the airport began significant infrastructure upgrades.

[6] This marked the beginning of the airport's transformation into a modern facility capable of handling more frequent commercial flights.

In 1967, Cathay Pacific began operating a twice-weekly Convair 880 jet service to Hong Kong with a stop in Manila.

[12] In 1969, a British consultancy firm was appointed to develop a Master Plan for the airport,[citation needed] which included proposals for significant upgrades, such as reinforcing and extending the runway to 2,987 meters to accommodate Boeing 707 and 747 jets, building a new terminal, and installing modern navigation and communication systems.

In 1992, the Department of Civil Aviation of Sabah was corporatised, and Malaysia Airports Holdings Berhad took over the management of KKIA.

A major renovation and expansion of Terminal 1 was approved in mid-2005 by the Malaysian federal government, with the project costing RM1.4 billion.

As part of these efforts, the Transport Ministry is exploring the acquisition of adjacent land to facilitate the expansion under the 12th Malaysia Plan.

Planned upgrades include extending the international terminal building by adding one additional gate, constructing new aircraft bays and developing a multi-level car park.

However, it faced widespread criticism for its necessity, the proposed site's rural location,[27] the inconvenience to passengers, and the lack of public transportation.

Additionally, KKIA was the first airport in Malaysia to welcome the Boeing 787 Dreamliner, operated by Royal Brunei during several product introductory flights in November 2013.

In 2006, Terminal 2 underwent a major renovation and extension to accommodate low-cost carriers, reopening on 1 January 2007 in conjunction with Visit Malaysia Year 2007.

The decision was opposed by AirAsia, and the airline refused to move despite a government directive to do so, missing the deadline five times as of 1 August 2015.

[18] The Terminal currently serves for cargo operators such as Raya Airways and several General Aviation companies such as Weststar and Layang-Layang.