Cortés skierował się w stronę wybrzeży Jukatanu. Pierwszą potyczkę z tubylcami z plemienia Tabasco stoczono zaraz po przybiciu do wybrzeża. Hiszpanie sterroryzowali Indian końmi, których ci nie znali i obawiali się. Tabaskowie poddali się i ofiarowali Cortésowi dary, a Hiszpanie ruszyli dalej, zakładając pierwsze miasto Nowej Hiszpanii – Veracruz. Następnie zatopiono potajemnie okręty, żeby zapobiec dezercji. Cortés dowiedział się również wtedy o niezadowoleniu wśród plemion wchodzących w skład państwa Azteków, gotowych sprzymierzyć się z każdym, z którym mogliby walczyć z ciemięzcami.

Hiszpanie w Tenochtitlán Aztekowie (Mexica) przybyli do doliny Meksyku w XIII wieku. W 1427 roku zawiązali federację plemienną, do której obok ich stolicy – Tenochtitlánu weszły także Tezcoco (Texcoco) oraz Tlacopan. Na czele hierarchicznie zbudowanego państwa stał władca będący jednocześnie najwyższym kapłanem boga wojny i Słońca – Huitzilopochtli.