Как только Грихальва вернулся, Диего Веласкес начал снаряжать флот для завоевания Мексики. Боясь назначить начальником Грихальву, пользовавшегося любовью солдат, губернатор поставил во главе экспедиции нового человека — Эрнандо Кортеса, «видного идальго» из Эстремадуры, щеголя и мота. «Денег у него было мало, зато долгов много», — говорит Б. Диас, в третий раз собравшийся идти на запад, на поиски счастья. Под залог своего имения Кортес получил от ростовщиков значительные средства и начал вербовку солдат.
Он обещал каждому долю в добыче и поместье с закрепощенными мексиканцами. Он набрал отряд в 508 человек (не считая ста с лишним матросов), взял с собой несколько пушек и 16 лошадей; на них он возлагал большие надежды, так как мексиканцы никогда не видели этих «страшных» животных и вообще не знали домашнего скота. Успех вербовки встревожил подозрительного губернатора. К тому же наушники убеждали его, что Кортес собирается завоевать Мексику лично для себя.
Веласкес послал письменный приказ сместить Кортеса. Тот ответил почтительным и насмешливым письмом с просьбой «не слушать ябедников». Веласкес приказал задержать флот и арестовать Кортеса. Тот вежливо сообщил, что «на следующий день выходит в море».
10 февраля 1519 г. девять кораблей Кортеса к «золотой стране» повел Антон Аламинос. На о. Косумель, где был храм, почитаемый народом майя, Кортес выступил в роли апостола христианства. По его приказу языческие идолы были разбиты вдребезги, капище превращено в христианский храм. Первая схватка с индейцами произошла на южном берегу залива Кампече, в стране Табаско. Сломив их сопротивление, Кортес послал три отряда внутрь страны. Встретив крупные военные силы, они отступили с большим уроном. Кортес вывел против наступающих все войско. Индейцы сражались с большой отвагой и не боялись даже пушек. Тогда Кортес ударил на них с тыла своим небольшим кавалерийским отрядом. «Никогда еще индейцы не видели лошадей, и показалось им, что конь и всадник одно существо, могучее и беспощадное». Через несколько дней касики прислали припасы и привели 20 молодых женщин. Кортес приказал их окрестить, а затем распределил среди офицеров. Одна из них, прославленная хронистами донья Марина, перешедшая впоследствии к Кортесу, стала переводчицей и оказала огромные услуги испанцам в борьбе против мексиканцев-ацтеков.
От Табаско флотилия прошла до о. Сан-Хуан-де-Улуа. 21 апреля испанцы высадились на берег материка и, чтобы обеспечить свой тыл, построили г. Веракрус. Вот как, по словам Диаса, основывали конкистадоры города в Новой Испании: «Избрали мы управителей города, на рынке водрузили позорный столб, за городом построили виселицу...» Итак, крест, позорный столб, виселица — вот три орудия освоения конкистадорами новых стран. У испанцев было огромное преимущество перед мексиканцами: огнестрельное оружие, железные доспехи, боевые кони. Но людей было так мало, что поход против многолюдной страны казался безнадежным. Кортес привлек на свою сторону обещаниями, подкупом, угрозами вождей окраинных народностей, угнетаемых господствующим народом — ацтеками.
Вожди, особенно из области Тласкала (точнее, Тлашкала), дали в помощь чужеземцам десятки тысяч воинов и носильщиков. Среди испанцев начались раздоры. Часть идальго, обеспеченных поместьями на Кубе, требовала возвращения на остров. Тогда Кортес пригрозил уничтожить весь флот, чтобы заставить даже нерешительных солдат наступать во что бы то ни стало. Часть пушек он все же снял с кораблей и взял в поход несколько десятков матросов, немного усилив таким образом наступающий отряд и гарнизон Веракруса.