Antrojo pasaulinio karo metu JAV turėjo problemų kuriant kodus, kurių Japonijos kriptologai negalėjo sulaužyti. Tie, kuriuos naudojo JAV armija ir Army Air Corp, buvo iššifruoti, o japonai galėjo perimti ir interpretuoti pranešimus apie kariuomenės judėjimą. 1942 m. grupė navajų indėnų prisijungė prie Jungtinių Valstijų jūrų pėstininkų, kur jie suformavo 282-ąjį būrį ir gavo užduotį sukurti kodą naudojant navajų kalbą. Šio padalinio nariai tampa žinomi kaip Navajo kodo kalbėtojai.
Projekto idėją sugalvojo Philipas Johnstonas, vyras, užaugęs misionierių šeimoje Navajo rezervate. Kai jis tarnavo Pirmajame pasauliniame kare, Johnstonas sužinojo atvejį, kai čoktau indėnų kariai naudojo savo gimtąją kalbą, kad suklaidintų vokiečius. Johnstonas buvo vienas iš riboto skaičiaus nevietinių žmonių, laisvai kalbančių navahų kalba, ir jis buvo įsitikinęs, kad dėl standartizuotos navahų abėcėlės ar kitos rašytinės kalbos medžiagos trūkumo tai buvo puikus kodo pasirinkimas.
Navajo yra sudėtinga tonacinė kalba, kurioje vienas vienodo tarimo žodis gali turėti visiškai skirtingas reikšmes, priklausomai nuo vartojamo tono. Skirtingai nuo daugelio indėnų kalbų, navajo kalba buvo nuolat kalbama šimtmečius ir vis dar paplitusi Naujosios Meksikos ir Arizonos rezervatuose. Nepaisant šio tęstinumo, šiuo metu navahai nepriėmė jokios formalios abėcėlės ar rašybos, kad sukurtų rašytinę kalbą. Tai buvo aiškus pranašumas, nes nebuvo rašytinių išteklių, kurie padėtų kriptologams iššifruoti perimtus pranešimus.
Pirmąją projektui įdarbintų navajų grupę sudarė 29 jaunuoliai. Po pagrindinių mokymų jų darbas buvo sukurti kodinius žodžius navajų kalba daugiau nei 400 karinių terminų. Kai kuriais atvejais jie galėjo naudoti terminus, kurie nupieštų paveikslą, pavyzdžiui, žodį kolibris, apibūdindamas naikintuvą. Kitose kodo frazėse buvo naudojami keli žodžiai angliškam terminui parašyti. Sukūrę kodą, šie originalūs Navajo kodo kalbėtojai sudarė visą žodyną, kurį turėjo įsiminti kiti vietiniai gyventojai, įdarbinti projektui.
Daugelis jaunų vyrų troško savanoriauti kaip Navajo kodo kalbininkai, o 1942–1945 m. daugiau nei 400 iš 540 Navajo jūrų pėstininkų tarnavo šias pareigas. Jie buvo paskirti į visas šešias jūrų pėstininkų divizijas ir aktyviai perdavė signalus visuose pagrindiniuose Ramiojo vandenyno mūšiuose, įskaitant Gvadalkanalą, Taravą, Saipaną, Iwo Jimą ir Peleliu. Mašinos, naudotos anksčiau karo metu koduoti, perduoti ir iššifruoti, užtruko 30 minučių, kad perduotų trijų sakinių pranešimus. Navajo kodo kalbantys žmonės tą patį žygdarbį sugebėjo atlikti vos per dvidešimt sekundžių.
Visi 411 kodo žodžių buvo įsiminti treniruočių metu, o karo arenoje nebuvo leidžiama įrašyti jokių rašytinių įrašų. Navajo kalbos žinovų įgūdžiai tapo legenda ir jiems buvo įskaityta daugybė amerikiečių gyvybių išgelbėjimo. Per pirmąsias 48 mūšio dėl Iwo Jima valandas šie kariai perdavė 800 pranešimų, nepadarydami nė vienos klaidos.
Navajo kodas niekada nebuvo pažeistas, o dėl jo strateginės svarbos visi Navajo kodo kalbininkai buvo prisiekę saugoti savo tarnybą. Tik 1968 m., kai projektas buvo išslaptintas, jų istorija iškilo į viešumą. 1982 m. prezidentas Ronaldas Reiganas pasiūlė pirmą oficialų grupės pripažinimą, o 2000 m. Kongresas priėmė įstatymą, kuriuo pagerbiami 29 Navajo jūrų pėstininkai, kurie sukūrė kodeksą Kongreso aukso medaliu.