Inaugurà la primera línia Amsterdam-Londres el 1920. Després de cinc anys d’experimentació, el 1929 fou inaugurada la ruta aèria de Batàvia, que era el servei més llarg de l’època. El 1939 s’estengué a Àfrica i l’Amèrica del Sud, i durant la Segona Guerra Mundial mantingué una línia Bristol-Lisboa. El 1946 fou la primera companyia europea a enllaçar amb els EUA. Té el centre d’operacions a l’aeroport de Schipphol (aeroport d’Amsterdam). Al setembre del 2003, la companyia féu pública la seva fusió amb Air France, formant el nou grup Air France-KLM. El grup esdevingué el primer del món de transport aeri de passatgers.