Die Gründung der Stadt unter dem Namen Tenochtitlán geht aztekischen Aufzeichnungen zufolge auf das Jahr 1325 zurück, als sich eine Schar von Nomaden aus dem Norden auf einer Insel im Texcoco-See ansiedelte. Die Azteken (eigentlich Méxica) ließen sich dort nach langen Jahren des Umherziehens, während deren sie sich von dem ernährten, was in festen Siedlungen freiwillig oder unfreiwillig zu bekommen war, nieder.
Ihrer Überlieferung zufolge hatten sie von ihrem Gott Huitzilopochtli den Auftrag erhalten, an der Stelle eine Stadt zu gründen, wo sie einen Adler fänden, der auf einem Kaktus sitzend eine Schlange verspeiste. Sie fanden ihn - auf einer Insel mitten im See. Adler, Schlange und Kaktus bilden das Zentralmotiv der heutigen mexikanischen Flagge.
Die tatsächliche Siedlungsgeschichte verlief jedoch vermutlich anders. Für die von Ort zu Ort getriebenen Méxica bedeuteten die kleinen Inseln inmitten des flachen Sees sicher in erster Linie einen guten strategischen Rückzugspunkt. Auf jeden Fall war die Stelle gut gewählt, denn der See versorgte sie mit Fisch, und der Boden der Chinampas, der schwimmenden Gärten, die sie angelegt hatten, war überaus fruchtbar.
Das wenige vorhandene Land hätte nicht ausgereicht, um die große Stadt zu ernähren, also wurden große Flöße gebaut und mit Erde beladen. Auf diesen im See gelegenen Nutzflächen züchtete man Blumen und Gemüse. Zwischen den Inseln und dem Festland wurden Dämme errichtet, die den Wasserstand des Sees regelten und so gebaut waren, dass die durch Brücken und Kanäle miteinander verbundenen Inseln im Notfall überflutet werden konnten. Zugbrücken schützten vor Angriffen (und verhinderten die Flucht).
Die Stadt auf der Insel erstreckte sich bald über mehr als 13 Quadratkilometer. Die Azteken gingen daran, ihren Machtbereich auszudehnen. Zuerst unterwarfen sie mit Waffengewalt, Intrigen und mit Hilfe wechselnder Verbündeter das Hochtal. Hundert Jahre vor der Conquista geboten die Azteken bereits über ein riesiges Reich, in dem ein reger Warenaustausch herrschte und dem selbst einige der entlegensten Gebiete des Landes tributpflichtig waren.