As others have written, the language is extremely difficult to begin with, having features not encountered together in most other languages, including tones, glottal stops, atypical word orders, nasal tones, consonants that are not found in English (for example), agglutination--"Stuck-together morphemes [word components]"--and so on. While related to languages of the "Athabaskan" group of languages, it would be totally incomprehensible to native speakers of, say, Ojibway.
To further make the Navajo code unbreakable, the speakers invented a code within the code, so that they did not, for example, use pure Navajo words to describe a high military official or a gun. Instead, they devised special words, so that when a Navajo soldier *not* a code-talker was interrogated by Japanese agents, he could honestly say, "Those guys are talking crazy! I have no idea what they mean."
Wiki explains some of this; also: my father was a cryptographer (code-breaker) in WWII.