Begay es miembro de la Nación Navajo. Creció en Nuevo México, donde su familia hablaba únicamente navajo. De niño, sabía solo una palabra en inglés: su nombre.
Eso cambió cuando tenía alrededor de 13 años. Fue entonces cuando Begay fue enviado a un internado. Cientos de miles de niños indígenas asistieron a escuelas similares. Los obligaban a abandonar sus culturas y no les permitían hablar sus lenguas nativas.
Mientras Begay estaba en la escuela, Japón atacó Pearl Harbor, una base militar estadounidense en Hawái. Al día siguiente, el 8 de diciembre de 1941, Estados Unidos entró en la Segunda Guerra Mundial.
Como muchos estadouni-denses, Begay quería unirse a la lucha. Casi dos años después, a los 17 años, se alistó en el Cuerpo de Marines de los Estados Unidos. Al llegar al campamento de entrenamiento, se enteró de que sería un codificador.
Las tropas estadounidenses necesitaban un código para enviar mensajes sobre sus planes de batalla. Tenía que ser difícil de entender para que el enemigo no pudiera descifrarlo. Como muy pocas personas hablaban navajo, el ejército decidió que era ideal para crear un código. Los hombres navajos que habían sido castigados por hablar su lengua nativa ahora la usarían para ayudar a Estados Unidos.
Begay pasó meses memorizando el código y creando nuevas palabras. Al final de la guerra, el código tenía más de 500 palabras.