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