De KNILM werd opgericht op 16 juli 1928 en bood vanaf 1 november 1928 retourverbindingen aan tussen Batavia en Bandoeng, respectievelijk Semarang (later doorgetrokken naar Soerabaja). Dit net werd geleidelijk uitgebouwd met vluchten naar andere eilanden in de archipel, zoals Palembang en Medan op Sumatra, de oliehavens Balikpapan en Tarakan op Borneo en vakantie-eiland Bali.

Al in 1930 kwam ook de eerste internationale luchtverbinding tot stand met Singapore. In 1938 volgde een luchtlijn naar het Australische Sydney, via Darwin, Cloncurry en Charleville. Ook zette de KNILM In de periode 1935-1937 drie Havilland Dragon Rapides in voor de luchtkartering van Nieuw-Guinea. Kort voor de Tweede Wereldoorlog werd het net binnen de archipel in oostelijke richting uitgebreid met bestemmingen zoals Ambon, waarvoor de KNILM speciale amfibievliegtuigen aanschafte.

Het leger gebruikte KNILM-vliegtuigen al vaak voor troepenbewegingen. Toen Japan Nederlands-Indië aanviel werden de vliegtuigen, voorzien van camouflagekleuren en extra brandstoftanks, ingezet voor evacuatievluchten en troepentransporten. Op 28 december 1941 ontkwamen bemanning en passagiers ternauwernood aan een aanval van Japanse jagers op het vliegveld van Medan en de DC-3 Nandoe PK-ALN.

Vlak vóór en na de Japanse invasie van Java op 1 maart 1942 werden alle KNILM-vliegtuigen met voldoende vliegbereik geëvacueerd naar Australië. Een aantal vliegtuigen werd daarna alsnog beschadigd of vernietigd bij Japanse luchtaanvallen. De elf resterende toestellen (3 Douglas DC-5, 2 DC-3, 2 DC-2 en 3 Lockheed Super Electra) werden half mei 1942 verkocht aan de Amerikaanse strijdkrachten.

In de jaren kort na de Tweede Wereldoorlog was geen normaal luchtverkeer mogelijk in Nederlands-Indië. Een poging, in 1946, om de KNILM opnieuw op te richten was geen succes. Een wekelijkse luchtlijn van Batavia over de Grote Oceaan naar Los Angeles, gevlogen met de viermotorige DC-4, werd al na enkele maanden gestaakt. Officieel werd de KNILM opgeheven op 1 augustus 1947. Toen nam de KLM de restanten over om met het KLM Interinsulair Bedrijf het luchttransport binnen de archipel te gaan exploiteren.

De KNILM-vloot omvatte: