Navajo aren't really a good example of "Native American" for cuisine purposes (although things like fry bread probably are the most recognizable instances of Native American cuisine for the general public).
The Navajo are fairly recent arrivals to the American Southwest, they are Athabascan in origin and likely not far removed from East Asia.
The Navajo arrived in the American Southwest from Canada/Alaska in the late 1300/ early 1400's. And the Spanish arrived to the area not much more than 100 years later bringing horses, sheep and European crops which were adapted to some extent by the natives.
Contrast that with groups like the Hopi or other Pueblo tribes who are descendants of peoples with thousands of years history in the area and who farmed native crops such as corn and squash for many many generations before the first Navajo (or Navajo ancestor to be proper) ever set foot in the area.
Point being, Navajo food isn't really Native American food much behind the level of Tacos. There was significant European influence during most of the time Navajo culture developed.
I think a lot of "real" Native American cuisine was probably something like berries and dried meat mixed with fat wrapped in a piece of skin. Or some inner pine bark if times were rough. Except for the farming tribes that had little bitty corn and some primitive squash. Probably not really that tasty IMOP.