Recent findings of long-distance Apachean movements from Promontory Cave have bearing on the early history of Diné (Navajo) people in the U.S. Southwest. Many archaeologists currently subscribe to a longstanding “late arrival narrative” that describes Navajo ancestors migrating from the northern Athabaskan world to the Southwest after AD 1300. On the other hand, there is no evidence in Diné oral tradition of a migration from the northern Athabaskan world, and proposed archaeological indicators of early Navajo sites (e.g., forked stick hogans) limit and essentialize a complex history. Diné clan histories describe events, places, and multicultural interactions during the 'Anaasází period (AD 700-1300) in great detail, revealing a far more interconnected and complex history of identity formation than currently presented by archaeologists. In this paper, we review elements of traditional history and recent archaeological findings—including Promontory-style moccasins from Southwestern collections—that complicate the late arrival narrative and suggest how a more culturally-informed archaeology of early Diné history might be put into practice.