W chwili przybycia do Doliny Meksyku w regionie znajdowało się już wiele miast-państw, z których najpotężniejszymi były Culhuacán na południu i Azcapotzalco na zachodzie. Mexikowie osiedlili się w pobliżu tego pierwszego po tym jak wcześniej zostali wypędzeni z przez Tepaneków z Azcapotzalco. W roku 1299 władca Culhuacánu, , pozwolił im osiedlić się na pustkowiach Tizapan, gdzie zaczęli się oni asymilować z kulturą Culhua. Po przegranej wojnie z mieszkańcami ich wódz został złożony w ofierze, a Mexikowie stali się wasalami Culhuacánu. W walkach po stronie suwerena odznaczyli się jednak wielkim męstwem, za co w nagrodę wydano im córkę wodza. Szlachetny rodowód Culhuacánu sięga korzeniami legendarnego miasta-państwa Tuli, a poprzez wżenienie się w ich rodziny Mexikowie przywłaszczyli sobie to dziedzictwo. Wydaną córkę poślubili zatem swemu bogu Huitzilopochtliemu obdzierając ją żywcem ze skóry, którą następnie założył jeden z kapłanów. Uciekając przed zemstą jej ojca Mexikowie ponownie zostali zmuszeni do wędrówki. mały|Wizja orła na kaktusie jedzącego węża Dopiero po 150 latach od przybycia do Tuli, w roku 1323, jak głosi aztecka legenda, Mexikowie ujrzeli orła siedzącego na opuncji jedzącego węża. Wizja ta była znakiem od boga wskazującym miejsce, gdzie mieli się osiedlić na stałe.