1519年2月10日、11隻の船に508人の剣士、100人の水兵、32人の弩射手、13人の小銃兵が乗り込んでハバナを出発した。船には10門の青銅製大砲、16頭の馬、火薬、弾丸、箭、多くの犬も積み込まれていた。コルテスが1518年10月23日にベラスケスから受け取った命令書は、グリハルバの捜索命令で、探検と交易は認められているが、居留地を造ったり植民を行うことは禁じられていた。 命令書の内容とは釣り合いの取れない軍隊だった。
コルテスはコルメル島で噂になっていたスペイン人の難破者を探した。2人のスペイン人がいることが分かり、アギラールという男がコルテスのマヤ語の通訳になった。
タバスコ川の河口で錨を下ろし、町から5キロ程離れた棕櫚の岬に部隊を上陸させると、それが住民を刺激し、彼らは武装してやってきた。アギラールに食料と水の補給を頼ませたが拒否された。戦いとなり、翌日にはタバスコの1万人以上の兵士が出てきた。コルテスの作戦の巧みさと彼らが全く知らなかった馬に非常に驚き、タバスコの兵士はパニックを起こして森に逃げ込んだ。
翌日タバスコの指導者が和平を乞いにやってきた。彼らの贈り物の中に20人の女がいた。その中にメキシコ貴族の娘でスペイン名ドーニャ・マリーナがいて、マヤ語とメキシコ語が使えた。以後コルテスの全ての交渉に彼女は重要な役割を果たしていく。タバスコの指導者たちは戦いに破れ、その面目を失っていた。タバスコ人はアステカ帝国の攻撃に対抗して、その臣下とはなっていなかった。コルテスがカルロス1世の臣下となるように求めたときに、一切の異議は出なかった。数日後、コルテスは祭壇を建てさせ街の有力者を集めてミサを行い、その祭壇を清潔に保つことを約束させた。
タバスコ人はメキシコの人々とは違う民族だった。一部はオルメカ文明を起こした人たちの末裔でもあった。彼らはヨーロッパ人が知らなかった、ゴムの樹を植え、ゴムの輸出もしていた。

1519年4月22日、コルテスはサン・ホァン・デ・ウルア島の対岸に上陸した。追放された神ケツァルコアトルが帰ってくると言っていた“一葦の年”でちょうどケツァルコアトルの日だった。
投錨して30分くらいで、モンテスーマが派遣していた偵察隊が挨拶をしにやってきた。翌日コルテスは陣地を築き、メシコ（アステカ帝国）の使者が贈り物を携えて訪ねてきた。
キューバ総督ベラスケスの支配から脱するために、コルテスはベラクルスの町を建設した。その頃のスペインの法律では、国王の許可が得られれば、植民地でも町を作り、官吏を選出できた。それらの官吏は国王に直接従属し、ほかの誰も命令することはできなかった。コルテスは国王の許可を求めるために、手紙を書き、モンテスーマからの贈り物の大部分を持たせてスペインに向かわせた。
（この頃のスペインでは獲得した利益の1/5を国王に税として納めることになっていた。コルテスは仲間の同意を得て贈り物の大部分をスペインに送った。これは神聖ローマ皇帝選挙にも役立った。）
コルテスを監視するためにベラスケスの命で同行していた人々は、この措置に反対したが、やがて意見を変え、彼らの指導者モンテホは町の高位の役職に就いた。法律を学んでいたコルテスの奇策だった。
一方モンテスーマはコルテスを神ケツァルコアトルだと思っていた。約束のときに上陸し、白い肌、蓄えられた髭は彼らの伝承と一致していた。できれは首都テノチティトランまで来ないで、再び東の楽園に帰ってくれることを期待していた。またケツァルコアトルは人身御供を嫌う神と考えられていた。
モンテスーマは贈る食料を少なくし、やがて止めさせた。このことで早く帰ってもらうためだった。

大航海時代年表　コルテス2　コルテス4