Durante a 2ª Guerra Mundial, os militares dos EUA sabiam que o inimigo estava a quebrar com sucesso alguns dos seus códigos. Além disso, as máquinas de cifra eram demasiado grandes e complexas para serem usadas pela infantaria em condições de combate.
Philip Johnston, um de apenas um punhado de não-Navajos que falavam o idioma nativo-americano Navajo, sabia que essa língua não escrita era extremamente complexa e falada apenas na região dos Navajo. Ele reuniu-se com o major-general Clayton B. Vogel dos Marines e sugeriu o uso de Navajos para comunicações militares seguras.
Os testes provaram que em condições simuladas de batalha, e com nenhum equipamento para além do próprio rádio, os Navajos podiam codificar, transmitir e descodificar uma mensagem curta em cerca de 20 segundos. As máquinas de cifra exigiam meia hora para fazer o mesmo trabalho, e sua transmissão podia ser decifrada pelo inimigo.
O general estava convencido e recomendou a contratação de 200 codificadores Navajo. Em Maio de 1942 o primeiro grupo de 29 codificadores Navajo foi recrutado. Eles desenvolveram um dicionário de código complexo, que atribuiu palavras Navajo com todos os termos militares modernos, que não existiam na língua Navajo ("tanque" e "aviões de caça", por exemplo , foram substituídos por "tartaruga" e "beija-flor"). O dicionário dos codificadores também incluia códigos para muitos termos ("batalhão" era "terra vermelha"), e vários códigos fonéticos alternativos para letras inglesas. O resultado foi de tal forma que mesmo um Navajo era incapaz de entender as suas mensagens, sem saber o seu código. O código inteiro teve que ser completamente memorizado pelos codificadores, nada foi escrito.
Os codificadores Navajo foram atribuídos a todos os batalhões da marinha, onde rapidamente ganharam reconhecimento pela sua habilidade, velocidade e precisão. Eles foram a melhor "máquina de cifra" da 2ª Guerra Mundial. Durante os dois primeiros dias da batalha de Iwo Jima, seis codificadores Navajo, trabalhando em turnos, enviaram e receberam quase mil mensagens codificadas sem um erro. Dizia-se que sem eles Iwo Jima não poderia ter sido tomada.
Serviços secretos japoneses, que ouviram as transmissões americanas e foram capaz de decifrar outros códigos americanos, foram incapaz de quebrar este. Desde que era um código falado, adivinharam correctamente que se tratava de um idioma nativo americano. Eles ainda forçaram um soldado Navajo do exército capturado para tentar quebrar o código, mas uma vez que os codificadores utilizavam um código, não a linguagem Navajo simples, ele também era incapaz de entender o que eles estavam dizendo.
Até o final da 2ª Guerra Mundial, havia cerca de 400 codificadores Navajo. Devido ao seu grande valor potencial para as guerras futuras, a existência de codificadores Navajo permaneceu durante décadas um dos segredos mais bem guardados da 2ª Guerra Mundial. Em 1981, o presidente Reagan concedeu-lhes um certificado de apreciação, e em 2001 eles receberam medalhas do Congresso. O dicionário dos codificadores Navajo encontra-se disponível no site da Marinha dos EUA.