Dalšímu rozvoji ale zabránila první světová válka, díky které navíc aeronautice začaly definitivně dominovat letouny těžší vzduchu. S koncem války se díky přebytku letců i strojů objevila řada pokusů o civilní leteckou dopravu. Z firem, které tehdy vznikaly, přežily první lety jen zlomek a ještě méně jich existuje dodnes.
Ani začátky KLM nebyly jednoduché. Například přes půl roku trvalo, než letecká firma, založená s dobrozdáním nizozemské královny Vilemíny, vůbec vypravila na linku první letadlo. Byl to navíc stroj pronajatý i s pilotem od britské společnosti Aircraft Transport and Travel, který z Londýna na Schiphol přepravil dva anglické novináře a zásilku novin. Do konce roku 1920 nebyla bilance KLM nijak oslnivá - firma přepravila jen 440 cestujících a 22 tun nákladu, navíc na příležitostných letech. Pravidelné linky se v nabídce objevily až v roce 1921.
Vývoj šel ale rychle kupředu a v polovině 20. let KLM nabízela pravidelné letecké spojení Amsterdamu se sedmi městy západní a severní Evropy (mj. s Londýnem, Bruselem a Paříží). Už v roce 1924 také doletěl první z fokkerů do Nizozemské východní Indie, dnešní Indonésie. Pravidelnou dopravu do jihovýchodní Asie aerolinky nabídly o pět let později a těšila se značnému zájmu. KLM se v té době řadily mezi několik málo leteckých společností, které měly v nabídce mezikontinentální linky.
Další výrazné změny přinesla polovina 30. let. Tehdy se v letovém řádu KLM objevila první linka přes Atlantik (na ostrov Curaçao na Nizozemských Antilách). V roce 1934 se pak otevřela i další nová kapitola, když se v leteckém parku objevila letadla od jiného výrobce než tradičního Fokkera. Byly to Douglasy DC-2, první z řady „décéček“, která KLM používaly. Stroje, které v licenci vyráběla Fokkerova továrna, našly rychle uplatnění hlavně na nejdelších linkách do Indonésie.
Do rozvoje letectví v Nizozemsku, jako v celé Evropě, ale tvrdě zasáhla druhá světová válka. KLM - až na odnož v Karibiku - přestala létat a také přišla o svá letadla. Po válce tak firma začínala vlastně od nuly. Díky příspěvku nizozemské vlády i dostupným americkým letadlům se ale rychle postavila znovu na nohy. A v roce 1962 se na strojích KLM poprvé objevilo logo, které dobře znají i dnešní cestující - korunka složená z několika geometrických tvarů a pod ní písmena KLM.
I přes nejtragičtější leteckou nehodou symbolem
Značka se stala symbolem rychle rostoucí letecké společnosti, která například jako jedna z prvních zařadila v roce 1971 do své flotily velkokapacitní letouny Boeing 747. Právě s nimi je ale spojena i nejtragičtější nehoda v dějinách KLM i světového letectví vůbec. V březnu 1977 se totiž Jumbo Jet v modrobílém nátěru na letišti v Santa Cruz de Tenerife na Kanárských ostrovech srazil s americkým letadlem téhož typu. Zahynulo tehdy 583 lidí na palubách obou letadel.
Ačkoli byl viníkem nehody nejspíš nizozemský kapitán, na pověsti KLM jakožto spolehlivého dopravce výjimečná tragédie nezanechala šrámy. V posledních letech se ale firma potýkala s rostoucí konkurencí, kvůli které dokonce v květnu před pěti lety samostatná KLM zanikla. Spojila se totiž s francouzským národním dopravcem Air France. Vznikla tak společnost Air France-KLM, která patří podle počtu přepravených cestujících i počtu letadel do první pětky na světě. Navenek ale obě firmy i nadále působí zvlášť a tak na nebi zůstávají i letadla s modrou korunkou.