Según la tradición azteca, sus antepasados habían surgido de la tierra sagrada de Chicomoztoc, la legendaria montaña de "las siete cuevas", un lugar de origen cósmico para muchos pueblos de Mesoamérica. No obstante, muchos relatos dicen que los aztecas procedían de la mítica isla de Aztlan en el noroeste, de donde procede su nombre, comenzando su migración hacia el sur, hasta el valle de México, en el año "1 pedernal" (1116 o 1168 d.C). Aztlan estaba rodeada de cañas y situada en una gran laguna: su nombre significa "el lugar de blancura" o "el lugar de las garzas".
Según el mito, durante el viaje, los aztecas fueron guiados por un ídolo parlante de Huitzilopochtli, su dios tribal de la guerra. Cuando se les unió un grupo de cazadores-recolectores nómadas de nombre mexica, el dios convenció a su gente para que adoptara el nombre y la forma de vida de éstos últimos, así como sus armas, el arco y la flecha. Vagaron por montañas y desiertos durante 20 años, sin permanecer nunca en un lugar, espoleados siempre por el espíritu visionario de Huitzilopochtli, que profetizaba grandes logros futuros para su pueblo. El dios hablaba a los mexicas a través de sus sacerdotes, diciéndoles cómo debían conquistar todos los pueblos del universo hasta convertirse en los señores y reyes del mundo. De acuerdo con esta deidad, los mexica debían recibir tributos de oro, esmeraldas, coral, plumas de quetzal, cacao y algodón.
El viaje mitico siguió hasta Culhuacán, la "montaña curva" y Chicomoztoc, aunque ambos lugares pueden ser el mismo. Luego siguió una serie de luchas internas, una de las cuales causó el abandono de la hermana de Huitzilopochtli, Malinalxochitl, que siguió hasta fundar la ciudad de Malinalco.
Los mexicas siguieron sus migraciones hasta Coatepetl ("montaña de la serpiente"), cerca de Tula. Aquí se produjo la concepción mágica del sobrenatural Huitzilopochtli por Coatlicue, "la de falda de serpientes", la madre tierra, a partir de una bola de plumas preciosas.
El dios embrionario fue avisado de que su celosa hermana, la diosa de la luna Coyolxauhqui, y sus 400 hermanos estrellas, los Huitznahua, tramaban matar a su madre y a él mismo. Anticipándose al asesinato, Huitzilopochtli salió ya adulto del vientre de su madre, un guerrero cósmico invencible, y con una serpiente de fuego cortó la cabeza a Coyolxauhqui y desmembró su cuerpo. Luego dispersó a sus hermanos estrellas por todo el cielo. Los mexicas salieron de Coatepetl, dirigiéndose a Tula, y de ahí al valle de México.