After the ancestors of most Native Americans crossed the Bering Land Bridge, about 12,000 BC, they split up and settled in different parts of North America. The Navajo started out as part of the Athabascans or Dene. Like other Athabascans, they settled in west-central Canada (modern Alberta or Saskatchewan).
Sometime around 1300 or 1400 AD, there was a global cooling pattern known as the Little Ice Age. So it was colder than usual in Canada. The Navajo and their relatives the Apache left the other Athabascans behind and headed south through the Great Plains. They mostly lived from bison hunting. They lived in tipis. And they used dog-sleds to move their things from one camp to another. (They didn’t have horses.) Navajo dogs were generally white, with black spots, and not very big (like spaniels).
“Navajo” isn’t actually what these people called themselves. It’s what their enemies called them. The Navajo called themselves “Dine,” which means “The People”. That’s the same as what other Athabascans called themselves.
By around 1400 AD, the Navajo reached the southwestern part of North America. They settled down there, in what is now Arizona. Their new neighbors were the Pueblo people. Pueblo people taught the Navajo how to farm corn and beans, and the Navajo began to get a lot of their food from farming.
By 1541 AD, the Navajo were in contact with Spanish traders. But they stayed independent for hundreds of years after that.