Bölgeden birçok kabile geçmesine rağmen Azteklere kadar hiçbiri kalıcı olarak yerleşmemiştir. Aztek efsanelerine göre, kuzeyin çöllerinden göç eden kabile, rahiplerin kehanet ettiği , bir kartalın kaktüs üzerinde bir yılan yediğini gördükleri ideal yerleşim yerine yeni şehirlerini kuracaktı. Kabile , kartalı küçük bataklık bir adanın üzerinde görmüş olmalı. Bu efsane , şu anda Meksika’nın sembolü olarak bayrağında ölümsüzleştirilmiştir. Tarihçilere göre, bu pek uygun olmayan yere yerleşmelerinin sebebi, diğer yerlerin daha güçlü kabileler tarafında ele geçirilmiş olması. Yine de bu durum Aztekleri yıldırmadı; chinampa denilen ve göle dikilen kazıklar üzerine konulmuş kamıştan yapılan dikdörtgen platformların üzerine toprak konularak yapılan bir tarım şeklini bularak ekilebilir alan miktarını arttırdılar. Tarihçilerin tahminlerine göre şehir 14.yüzyılda kurulmuştur. En çok öne sürülen tarih 1325 yılıdır.
İspanyol Fatih (Conquistador) Hernan Kortez Tenochtitlan’a 8 Kasım 1519’da gelmiştir. O zamanlar dünya üzerindeki en büyük şehirlerden biri olduğuna inanılmaktadır; Avrupa’da sadece Paris, Venedik ve İstanbul daha büyüktü. Yaklaşık olarak 60 ila 130 bin kişi arasında insanın yaşadığı tahmin edilmektedir.
Şehir campan adı verilen dört bölgeye ve her campan 'da calpulli adı verilen 20 mahalleye ayrılmıştı. Her calpulli 'den tlaxilcalli adı verilen caddeler geçmekteydi. Şehri baştan sona geçen ve anakaraya uzanan üç ana cadde vardı. Bernal Díaz del Castillo tarafından yazıldığına göre her biri on at genişliğindeydi.
