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