Contary to popular conception, the Navajo code did not consist of simply speaking in Navajo. The code talkers developed several alphabet codes in which each letter of an English message was converted to an English word starting with that letter, and then the Navajo translation of that word would be transmitted. See the link at the end of the article to see the now-declassified codebook. The codetalkers memorized all these variations.
The Japanese never cracked the spoken code, and high military officers have stated that the United States would never have won the battle of Iwo Jima without the secrecy afforded by the code talkers, yet the codetalkers received no recognition, medals or honors until 2002. By then, most of them had passed away, many almost destitute on the Navajo reservation.
Native American languages were chosen for several reasons. Most importantly, speakers of these languages were easy to recruit inside the United States, while the languages were virtually unknown in Europe and Japan. Hitler did know about the successful use of codetalkers during World War I and sent a team of some thirty anthropologists to learn native languages before the outbreak of World War II, however it was impossible to learn all the many languages and dialects that existed.
Furthermore, an unfamiliar human language is harder to "crack" than a code based on a familiar language. The languages chosen had little written literature, so that researching them was difficult for nonspeakers. In addition, nonspeakers would find it extremely difficult to hear accurately the unfamiliar sounds of these languages. Finally, the additional layer of an alphabet code was added to prevent interception by native speakers not trained as codetalkers, in the event of their capture by the Japanese.
The Navajo spoken code is not very complex by cryptographic standards of the time, and might have been broken if a native speaker and trained cryptographers worked together effectively. The Japanese had an opportunity to do so when they captured Joe Kieyoomia in the Philippines in 1942. Kieyoomia, a Navajo Seargeant in the U.S. Army, was ordered to interpret the radio messages. They made no sense to him, and when he reported that he could not understand the messages, his captors tortured him. Given the simplicity of the alphabet code involved, it is probable that the code could have been broken easily if Kieyoomia's knowledge was exploited more effectively by Japanese cryptologists.