A kódbeszélők története az első világháború végén kezdődik, amikor egy bizonyos Lawrence százados véletlenül felfigyelt arra, hogy két indián származású katonája csaktó nyelven társalog. Megszületett az ötlet, és Lawrence összegyűjtötte a zászlóaljban szolgáló mind a nyolc csaktó katonát. Később már a 36. gyalogsági hadosztály tizennégy csaktó katonáját képezték ki arra, hogy a híradófeladatokat a saját nyelvükön lássák el.
A német katonai vezetés tudott az első világháborús indián kódbeszélőkről, ezért a második világháború előtt Hitler harminc „néprajzkutatót" küldött az Államokba, hogy az indián nyelveket tanulmányozzák. A sokszor még ábécével sem rendelkező nyelv és nyelvjárás megismerése - főleg az írásbeliség hiányában - azonban túl nagy feladatnak bizonyult. Annyit viszont elértek a németek, hogy az amerikai katonai vezetés - akik tudtak a német kutatók tevékenységéről - csak kis létszámban alkalmazott indián kódbeszélőket az európai hadszíntéren. A normandiai partraszállásban tizennégy komancs kódbeszélő vett részt.
A navahó nyelv használatát Phillip Johnston javasolta, aki egyike volt azon huszonnyolc fehér amerikainak, akik ismerték a nyelvet. Johnston egy misszionárius fiaként navahó rezervátumban nőtt fel a század elején. Sokat hallott a hadseregben szolgáló komancs kódbeszélőkről, és ekkor támadt az ötlete, hogy a navahó mint az egyik legnépesebb, de írásbeliséggel nem rendelkező törzs nyelve különösen alkalmas lehet a feladatra. Az amerikai tengerészgyalogság lelkesen támogatta Johnston javaslatát, és rögtön kétszáz kódbeszélőt igényeltek, kezdetben azonban csak harminc alkalmas személyt sikerült találni. A navahók az üzeneteket nem csupán a saját nyelvükre fordították, hanem - a memorizálást megkönnyítendő - kitaláltak egy meglehetősen bonyolult rendszert, amelyben az angol katonai szavak, fogalmak mindegyikének megfeleltettek egy navahó szót. Az üzenetek a szavak értelmetlen, nyelvtanilag helytelen sorozatának tűntek.