Según la leyenda, cumplidos 130 años después del la creación del quinto Sol, los aztecas salieron de Chicomóstoc --lugar de las Siete Cuevas--, de donde partieron junto a los xochimilca, los chalca, los cuitlahuaca, los de Tacuba, Coyohuacan, Azcapotzalco y Culhuacan. Más concretamente, Aztlan --lugar de las Garzas--, localizado posiblemente en el occidente de México, fue de donde partieron, uniéndose a las tribus anteriores en Culhuacan, lugar donde recibieron por dios a Huitzilopochtli (Colibrí Hechicero), que tenía la valiosa habilidad de hablar para darles buenos consejos. Iniciaron su peregrinaje (en un año "Ce Técpatl") desde principios del siglo XII de la Era Cristiana, en busca de la Tierra prometida por su dios tutelar: una zona pantanosa en la cual estuviera un nopal sobre una roca y sobre él una águila devorando una serpiente.
Cuatro personas guiaban al pueblo --los cuales llevaban a cuestas al recién adquirido numen--: Quauhcóatl, Apanécatl, Tezcacoácatl y Chimalma (ésta última, una mujer).
Se desplazaron hacia el sur, por el bajío, dedicados a la caza y la agricultura, y en cada lugar donde se establecían momentáneamente, hacían un altar a su dios para adorarlo. Permanecían un año o más en un lugar determinado, mientras los exploradores buscaban nuevas tierras donde asentarse.
Los aztecas fueron los últimos en llegar al Valle de México, por Tula y Zumpango, dominado entonces por señoríos de origen tolteca. Fueron mal recibidos y vagaron durante años sin poder establecerse. Buscaron refugio en el señorío de Azcapotzalco, y con la autorización de éstos se establecieron en Chapultepec. En este lugar fue sacrificado el hijo de una mujer (tenochca) que los chichimecas habían raptado y llevado a Mechuacan (Michoacán). Huitzilopochtli se les apareció a los aztecas, y les dijo que enterrasen el corazón del sacrificado en un lugar que se llamó Tenuchtitlan, porque en aquel lugar había de ser su morada, y allí estaría él; lugar donde posteriormente fue fundado México-Tenochtitlan.
