Изменения произошли и в его личной жизни: в Сантьяго, в присутствии губернатора, Кортес отпраздновал свою свадьбу с Каталиной Суарес, происходившей из мелкопоместного дворянства Гранады.

Когда Диего Веласкес начал в порту Сантьяго снаряжать флотилию (10 судов) для новой экспедиции с целью завоевания Мексики, он поставил во главе экспедиции Эрнандо Кортеса, "видного идальго" из Эстремадуры, щеголя и мота. "Денег у него было мало, зато долгов много, - говорит хронист Берналь Диас дель Кастильо. - Энкомьенда (поместье) его была не плоха, да и индейцы его работали на золотых приисках, но все уходило на его собственную особу, на наряды молодой хозяйки и на приемы гостей. Он имел тонкое обхождение и дар речи".

Под залог имения Кортес получил от ростовщиков большие средства деньгами и товарами и начал вербовку солдат, обещая всем долю в добыче и поместье с закрепощенными индейцами. Он набрал отряд в 508 человек, не считая 100 с лишним матросов, взял с собой несколько пушек и 16 лошадей. Особенно большие надежды он возлагал на лошадей, так как мексиканцы, как и жители Антильских островов, никогда не видели этих "страшных" животных и вообще не знали никакого домашнего скота.

Успех вербовки встревожил подозрительного губернатора. К тому же приближенные убеждали его, что Кортес собирается завоевать Мексику лично для себя. Веласкес послал письменный приказ сместить Кортеса и передать команду другому. Кортес ответил почтительным и насмешливым письмом с просьбой "не слушать наушников и помешанного старика астролога". А своему отряду он приказал привести оружие в порядок. Тогда Веласкес приказал задержать флот и арестовать Кортеса. Тот вежливо написал ему, что "на следующий день выходит в море и остается его покорным слугой".

10 февраля 1519 года девять кораблей вышли из Гаваны. Флотилию Кортеса к "Золотой стране" за полуостровом Юкатан повел Антон Аламинос.

18 февраля флот двинулся в Макаку, небольшой порт примерно в 80 километрах западнее Сантьяго. Здесь участники экспедиции считали себя недосягаемыми для погони наместника. В Тринидаде Кортес пополнил запасы и приказал поднять свой штандарт черного бархата, на котором были изображены красный крест, окруженный белыми и синими языками пламени, и надпись на латинском "In hoc signo vinces" ("С этим знаком побеждаю"). Под командованием Кортеса уже находились знатные и известные идальго, поэтому к экспедиции присоединялись все новые и новые люди. В конце концов, в завоевании Мексики приняло участие около 2000 испанцев. С этим отрядом Кортес отправился в самый рискованный и трудный военный поход своего века.

В марте суда миновали Чампотун и вошли в широкий залив Кампече. Вскоре Кортес достиг устья Рио-Табаско, или Рио-Грихальва Именно в стране Табаско произошло первое столкновение испанцев с индейцами. Для того чтобы завязать контакты с туземцами, было решено отправиться вверх по реке, однако это было связано с многочисленными трудностями из-за мелей. Высадке на берег воспрепятствовали индейские воины, размахивавшие копьями. На следующий день испанской коннице удалось обратить противника в бегство. Сломив их сопротивление, Кортес захватил прибрежное селение, именем короля вступил во владение этой страной и послал три отряда внутрь страны. Они встретили там крупные военные силы и отступили с большим уроном. Кортес вывел против наступающих все свое войско. Индейцы сражались с большой отвагой, не боялись даже пушек, но бежали от небольшого кавалерийского отряда, который атаковал их с тыла.