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