They had to use other Navajo words for new items that they originally had no words for in Navajo.
like for example a tank was a turtle and an aircraft carrier was a frog.
We visited the Hall of State at the Texas state fair this weekend. An exhibit on WWI mentioned Cherokee code talkers in WWI. Had never heard of that.
They also developed a three-deep code for the phonetic alphabet. For each Roman letter, they chose an English word, like A=Armadillo. Then they used the Navajo word for “armadillo” to represent A. They made three versions of this. Then they chose code words to indicate which version was in play in a certain transmission, and sometimes they’d change mid-message.
It wasn’t just that the Navajo language was unwritten, unknown, and incredibly difficult: they also put some serious work into making a real code. In the European theater, some Native American soldiers used their tribal languages on a more ad-hoc basis. A Comanche Code Talker from the 45th Infantry spoke to our homeschool group in Norman, OK, back in the late 90s.