Prapoczątki Azteków opisuje średniowieczny dokument indiański, zwany także „Wstęgą Wędrówki” (hiszp. Tira de la Peregrinación). Opowiada on, iż Aztekowie natknęli się pewnego dnia na kamienną głowę boga Huitzilopochtli, która wydawała z siebie dziwne świszczące dźwięki. Huitzilopochtli obiecał im, że uczyni ich panami całego Meksyku i wskaże im miejsce do osiedlenia się, jeżeli tylko zabiorą kamienną głowę ze sobą. Zgodnie z legendą, Aztekowie posłuchali swego nowego boga i wyruszyli z mitycznej krainy Aztlán (Miejsce Czapli), znajdującej się daleko na północy, przypuszczalnie w rejonie dzisiejszego amerykańskiego stanu Nowy Meksyk. Osiedlili się na krótko w miejscu zwanym Chicomóztoc (Siedem Grot – mityczne miejsce wymieniane w mitologiach wielu ludów Mezoameryki). Następnie w 1163 przybyli do Coatepez (według archeologów w pobliżu miasta Tula) i ostatecznie w 1168 do samej Tuli – oddalonej o 64 kilometry od brzegów jeziora Texcoco. Po przybyciu do Kotliny Meksykańskiej Aztekowie osiedlili się w pobliżu miasta Culhuacán. Po przegranej wojnie z mieszkańcami miasta ich wódz został złożony w ofierze, a oni sami stali się wasalami Culhuacán. Walcząc po stronie suwerena odznaczyli się wielkim męstwem, za co w nagrodę otrzymali córkę wodza za żonę. Aztekowie poślubili ją swemu bogu – Huitzilopochtli, czyli obdarli ją żywcem ze skóry, w którą ubrał się jeden z kapłanów. Uciekając przed zemstą jej ojca, Aztekowie osiedlili się na bagnistej wysepce na jeziorze Texcoco. Dopiero po niemal 200 latach od przybycia do Tuli, po ciągłym poszukiwaniu miejsca do zamieszkania w okolicach jeziora, bóg Huitzilopochtli wskazał Aztekom miejsce na ostateczną siedzibę – według azteckiego kalendarza był to rok 1325 – na niewielkiej wyspie u źródeł strumienia. Pod skałą, z której wypływał, ujrzeli Aztekowie kaktus, na którym orzeł pożerał węża. Kapłani ogłosili, iż jest to długo oczekiwany znak od Huitzilopochtli, wobec czego Aztekowie na wyspie założyli miasto Tenochtitlán – Miejsce Owocu Kaktusa lub Kaktusowa Skała. W rzeczywistości powód założenia miasta na wyspie mógł być o wiele bardziej prozaiczny: teren wokół jeziora w chwili przybycia Azteków był już od dawna podzielony między silne i zorganizowane miasta a nowo przybyłym zwyczajnie mogło brakować siły do podbicia któregoś z sąsiadów.