Begay es miembro de la Nación Navajo (ver recuadro). Su fecha de nacimiento exacta se desconoce. Creció en Nuevo México, donde su familia hablaba únicamente navajo. De niño, Begay solo sabía una palabra en inglés: su nombre.
Eso cambió cuando fue enviado a un internado a los 13 años, más o menos. Cientos de miles de niños indígenas asistieron a escuelas similares, donde los obligaban a abandonar sus culturas y les prohibían hablar sus lenguas nativas.
Begay estaba en la escuela, cuando Japón atacó la base militar estadounidense en Pearl Harbor, Hawái. Al día siguiente, el 8 de diciembre de 1941, Estados Unidos entró en la Segunda Guerra Mundial.
Begay quería alistarse en el ejército, pero era demasiado joven. En agosto de 1943, cuando tenía alrededor de 17 años, se enlistó en el Cuerpo de Marines de los Estados Unidos. Al llegar al campamento de entrenamiento, se enteró de que sería un codificador.
El ejército estadounidense necesitaba un código secreto para enviar mensajes que los japoneses no pudieran descifrar. Si el enemigo lograba comprender el código, las vidas de las tropas estadounidenses correrían peligro.
Como muy pocas personas hablaban navajo, el Cuerpo de Marines decidió que esa lengua sería el punto de partida ideal para crear un código secreto. Los hombres navajos que habían sido castigados por hablar su lengua nativa ahora la usarían para ayudar a ganar una guerra.
Begay memorizó cada palabra del código durante meses y ayudó a crear nuevas. Al final de la guerra, el código tenía más de 500 palabras.