Retkikuntaan kuului 11 laivaa, se oli siis melkoinen. Mutta ennenkuin vielä ennätettiin matkaan lähteä, alkoi Velasquez, uskottujensa varottamana, epäillä, että Cortes ehkä oli saanut liian suuren sotavoiman johtoonsa ja että se ehkä rohkaisisi häntä aivan itsenäisesti toimimaan. Hän näyttää päättäneen peruuttaa Corteksen nimityksen; mutta tämä, pahaa aavistaen, lähtikin kiiruimman kautta Santiagosta, vaikka varustukset vielä olivat keskeneräiset. Hän purjehti ensinnä Trinidadin kaupunkiin, joka on etelärannalla, samoin kuin Santiagokin, pestasi sieltä vielä 100 Grijalvan mukana ollutta miestä ja kiersi sitten pohjoisrannalle Havanaan. Velasquez lähetti sikäläisille viranomaisille käskyn vangita Corteksen ja kielsi tätä purjehtimasta, ennenkuin hän oli itse ennättänyt Havanaan. Mutta Cortes semmoisia viestejä saatuaan vain kiirehti sitä enemmän, eivätkä Havanan viranomaiset uskaltaneet tehdä väkivaltaa miehelle, jolla oli niin melkoiset voimat käytettävänään. 18 p. helmikuuta 1519 Cortes laivoineen ulkoni merelle Cuban länsipäästä. Retkikuntaan kuului 400 asemiestä, niitten joukossa 13 pyssymiestä ja 32 jousimiestä, 16 ratsumiestä, 10 suurta pronssitykkiä ja 4 pientä kenttätykkiä, ynnä 200 intianisoturia. Kaksi pappia oli mukana; heidän määränsä oli kastaa intianit ja tehdä loppu epäjumalanpalveluksesta ja ihmisuhreista. Luotsi, joka oli ollut mukana kaikilla edellisilläkin matkoilla, opasti laivaston Yucatanin rannalle, Cozumelin saaren luo. Saaren asukkaat ensinnä pakenivat, mutta palasivat sitten takaisin ja sallivat Espanjalaisten hävittää heidän veriset alttarinsa ja pyhittää heidän temppelinsä kristitylle jumalanpalvelukselle.
Jo edellisellä matkalla oli tällä rannalla kuultu asukkaitten matkivan »castilla» sanaa, jonka tarkotusta ei kuitenkaan käsitetty. Cortes paikalla aavisti, että rannalla oli jo ennen käynyt espanjalaisia, ja eräältä päälliköltä kuultiinkin, että maalla vielä oli kaksi espanjalaista vankina. He olivat viimeiset henkiin jääneet Balboan v. 1512 lähettämän laivan miehistä; muut olivat Mayat jumalilleen uhranneet. Toinen oli munkki, Aguilar nimeltään; hän oli vankeudessa oppinut maan kieltä, ja Cortes sai hänestä nyt hyvän tulkin.
Tabascossa.
Pitkin Yucatanin rantaa purjehdittiin sitten Grijalva-joen suuhun, jossa asukkaat ottivat Espanjalaiset vihamielisesti vastaan. Syntyi kahakka, joka alkoi jo vedessä, mutta Espanjalaiset kaalasivat maalle, ratsuväki ja tykistö puuttuivat tappeluun ja Tabascolaiset, joita lienee ollut noin 40,000 miestä, hävisivät, hävisivät varsinkin peljästyksestä, sillä he luulivat ratsumiehiä hirviöiksi, joita oli mahdoton vastustaa. Seuraavana päivänä kasikit tarjosivat rauhaa, tuoden muitten lahjain mukana 20 orjatarta. Näistä yksi, Mexicosta orjaksi tuotu ylhäinen nainen, miellytti Cortesia niin suuresti, että hän piti hänet omanaan ja eli hänen kerallaan kuin vaimon kanssa, vaikkei liittoa vihkimys laillistuttanut. Tämä nainen, joka sitten tulkkina ja maan tuntijana oli retkikunnalle arvaamattomaksi avuksi, sai Espanjalaisilta Doña Marinan nimen.
Cortes sai Tabascossa ensimäiset tiedot sisämaassa olevasta suuresta valtakunnasta, Mexicosta, ja kuultuaan sen komeudesta ja rikkaudesta päätti oikopäätä lähteä sitä vallottamaan. Kun Tabascon päälliköt oli kastettu kristinuskoon, purjehdittiin huhtikuussa 1519 edelleen Mexicon rannikolle.
Mexicon rannalla.
Muutaman päivän kuluttua noustiin maihin nykyisen Vera Cruzin paikoille, kuivalle aukealle hiekkarannalle. Maanasukkaita alkoi keräytyä joka puolelta. He auttoivat Espanjalaisia rakentamaan itselleen majoja suojaksi polttavaa auringonpaistetta vastaan ja toivat runsaasti kaikenlaisia maan tuotteita kaupan. Tämä ranta kuului Tabascossa mainitulle sisämaan valtakunnalle, ja pian saapuikin aztekilainen maaherra tiedustelemaan vierailun tarkotusta. Cortes ilmotti, että hänet oli lähettänyt mahtava ruhtinas meren takaa ja että hänellä oli sanoma vietävä Mexicon hallitsijalle, Montezumalle. Maaherra ylpeästi vastasi ihmettelevänsä, että Cortes luuli pääsevänsä hallitsijan puheille, vaikka oli vasta pari päivää maassa ollut, mutta lupasi kuitenkin lähettää pikasanoman vieraitten tulosta ja aikeista. Rannikolta oli nimittäin pääkaupunkiin erinomaisesti järjestetty postiyhteys. Aina puolentoista penikulman päässä oli asema, josta airut paikalla lähetettiin sanoman keralla edelleen juoksemaan. Tämä yhteys oli niin nopea, että Montezuma vuorokaudessa saattoi saada tuoretta kalaa Mexicon lahdesta, vaikka väliä on yli 400 kilometriä. Maaherra antoi Cortekselle lahjaksi hienoja pumpulikudoksia, kalliita sulkaviittoja, kultakoristeita, ja sai tältä vastalahjaksi hallitsijaa varten leikkauksilla kirjaillun tuolin ja koko joukon lasiesineitä; näillä oli jalokiven arvo maassa, jossa ei tekolasia vielä tunnettu. Eräällä Corteksen miehistä oli päässään teräskypäri, joka maaherran mielestä oli hyvin samanlainen kuin aztekilaisen sodanjumalan päähine. Hän sen vuoksi pyysi saada senkin muitten lahjain joukkoon, johon Cortes puolestaan mielellään suostui, pyytäen korvaukseksi vain — kypärin täyden kultahiekkaa. Sillä ajalla kun tätä keskustelua kesti, oli eräs maaherran palvelija ahkerasti piirustanut värillisiä kuvia kaikista esineistä, mitä hän näki muukalaisten leirissä. Kuvatkin oli lähetettävä Montezumalle, jotta hän saisi oikean käsityksen näistä merkillisistä vieraista. Cortes oli tästä ylen mielissään, ja antaakseen hallitsijalle vielä täydellisemmän käsityksen itsestään, hän pani toimeen suuren aseleikin. Ratsumiesten nopeat liikkeet, aseitten välke auringonpaisteessa, torvien toitotus ja »vesihuoneitten» hiljainen kelluminen aalloilla, kaikki nämä seikat herättivät kokoontuneessa kansassa suunnatonta ihmettelyä. Mutta tykkien paukkuessa ja tulen ja savun tuiskiessa niitten kidoista ihmettely muuttui peloksi ja kammoksi. Maaherra nyt käsitti, että niin mahtavia vieraita oli kohdeltava hyvästi, jonka vuoksi hän käskikin alamaisiaan tuomaan muukalaisille ruokatavaroita ja kaikkea, mitä he tarvitsivat.
Montezuman lähettiläät.
Kauaa ei tarvinnut odottaa, ennenkuin pikalähetit olivat taivaltaneet pääkaupunkiin ja sieltä oli saapunut Montezuman, Aztekkien hallitsijan lähetystö, tuoden muukalaisille kalliita lahjoja. Lähettiläät vietiin Corteksen telttaan. He antoivat levittää maahan hienoja kankaita, ja orjat asettivat niille hallitsijan lähettämät lahjat, kilpiä, kypäriä ja haarniskoita puhtaasta kullasta, kaula- ja rannerenkaita samasta metallista, sandaleja, viuhkoja, höyhentöyhtöjä, taidokkaasti valmistettuja kultalintuja, esirippuja ja puuvillakankaita, jotka olivat pehmeitä ja hohtavia kuin silkki, ja kaksi suurta kullasta ja hopeasta valmistettua kilpeä, jotka kuvasivat aurinkoa ja kuuta. Ne olivat vaununpyörän kokoiset ja ainakin 20,000 kultapeson arvoiset. Mutta samalla Montezuma kehotti muukalaisia kiiruimman kautta lähtemään maasta pois.
Quetzalcoatl.