The story
The idea is usually credited to Philip Johnston, a civil engineer who had grown up on the Navajo Nation as the son of a missionary and spoke some Navajo. In early 1942 he suggested to the Marine Corps that the language could carry secret messages, and a demonstration convinced them. That spring the first group of 29 Navajo recruits went through boot camp and then worked out the code themselves.
The code had two layers. The first was an alphabet: an English letter was sent as a Navajo word for something beginning with that letter. The second, more important layer was a vocabulary of a few hundred code words for military terms, drawn from everyday life: aircraft were named after birds, ships after creatures of the sea, a tank was a tortoise and bombs were eggs. Code talkers learned it all by heart; nothing was carried into battle on paper.
In the field
Eventually several hundred Navajo Marines served as code talkers, most often counted at around 400, in every Marine division in the Pacific, from Guadalcanal to Okinawa. At Iwo Jima a signal officer later said that six code talkers had worked around the clock in the first days and sent and received more than 800 messages without an error. A message that took a machine half an hour could be passed in minutes.
The code was revised during the war. Because the alphabet could have been attacked by counting letters, the 1945 dictionary gave common letters several alternative words, so that E might be elk, ear or eye.
Other code talkers
The Navajo were not the first. In October 1918, in the last weeks of the First World War, Choctaw soldiers in the US Army passed messages in their language during the Meuse-Argonne offensive. In the Second World War, Comanche soldiers landed on Utah Beach in Normandy with the 4th Infantry Division, and Meskwaki soldiers served in North Africa. Men from many other nations, including the Hopi, Cherokee and Lakota, did similar work.
For decades the code talkers could not speak about it: the code stayed classified until 1968, in case it was needed again. Recognition came late. In 2001 the original 29 received the Congressional Gold Medal, and the others the Silver Medal; in 2008 Congress recognised the code talkers of many other tribes.
How it was broken
It never was. Navajo was rarely written, had very few speakers outside the Navajo Nation, and its grammar and sounds are very unlike Japanese or English. Even a fluent Navajo speaker who had not been trained in the code would have heard only a strange list of words: turtles, eggs, hummingbirds, iron fish.
The cost fell on the men themselves. Code talkers were shadowed by bodyguards in the field, and some were stopped by their own side because they were mistaken for the enemy.