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 probably started out as part of the Athabaskans, and settled in west-central Canada (modern Alberta or Saskatchewan).
A Navajo dog today
Sometime around 1300 or 1400 AD, maybe because of a global cooling pattern known as the Little Ice Age, the Navajo and their relatives the Apache left the other Athabaskans behind and began to travel south through the Great Plains. They mostly lived from bison hunting, living in tipis and using 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 they called themselves; it's what their enemies called them. The Navajo called themselves "Dine," which means "The People".
By around 1400 AD, the Navajo reached the southwestern part of North America, and they settled down there. The Pueblo people who were their new neighbors 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, though they stayed independent for hundreds of years after that.