Первый поход внутрь страны, но еще в пределах приморской низменности, был совершен под командой Педро Альварадо. С большим отрядом он двинулся за припасами на юго-запад от Веракруса, вверх по долине реки Котастла. Приречные индейцы бежали, но в их жилищах солдаты нашли много птицы, маиса и овощей.

Раздобыв съестные припасы, войско Кортеса двинулось берегом на север к той местности, откуда приходили враждебные Монтесуме индейцы, и вступили в область Семпоалу, населенную тотонаками - многочисленным тогда народом, порабощенным завоевателями-ацтеками. Жители и здесь бежали при виде испанцев и особенно их коней.

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

Монтесума прислал Кортесу новые дары, правда, гораздо менее ценные, чем раньше. Эрнан передал Монтесуме, что сам придет к нему на свидание в его столицу, которую испанцы называли Мехико, а ацтеки - Теночтитлан.

От Семпоалы большой испанский отряд во главе с Кортесом, сопровождаемый двумя тысячами тотонакских воинов, впервые поднялся на Мексиканское нагорье и после трехдневного похода вступил в область, населенную индейцами, враждебными тотонакам, но, как и они, порабощенными ацтеками. Заключив с ними союз и примирив с тотонаками, Кортес вернулся в Семпоалу.

Вернувшись в Веракрус, Кортес стал готовиться к военному походу в город Мехико.

В середине августа 1519 года несколько сот испанцев, сопровождаемых двумя с лишним тысячами союзных индейцев, из них около половины носильщиков, тащивших на себе пушки и припасы, выступили из Семпоалы на запад. (Обычно дают такой численный состав войска Кортеса: 400 пехотинцев, 15 всадников, 1300 индейских воинов и около 1000 носильщиков; из них 200, сменяясь, тащили на себе семь пушек.) В первые же дни, поднявшись на Мексиканское нагорье, войско прошло через город Халапа в горную крепость у массива Наукампатепетль (вершина - 4282 метра), обогнуло его и вскоре вступило в почти безлюдную местность, где испанцы, привыкшие к тропическому климату Кубы, и особенно индейцы из приморской полосы Мексики очень страдали от холода и резкого ветра.

Когда же войско подошло к городу Хонакотлан, испанцам показалось, что они попали в совершенно другую страну; изменился и внешний вид городов: "Белели крыши хижин, а дома касиков, храмы и множество часовен - все очень высокие здания - были покрыты белой штукатуркой".

Тотонаки советовали идти через страну Тласкалу, жители которой ненавидели ацтеков. Но тласкальцы, узнав, что с войском следует много данников Монтесумы, решили, что это враги, собрали против них тысячи воинов, трижды вступали в бой, причем убили нескольких испанцев и многих ранили.

Решено было освободить пленных тласкальцев и послать их к каемкам с разъяснением, что испанцы не союзники Монтесумы, и с предложением мира. А так как у тласкальцев потери были очень велики, то они заключили с Кортесом мир, обеспечили его войско съестными припасами, пригласили войти в свою столицу. Как раз в это время в лагерь пришли послы от Монтесумы с сообщением, что он согласен платить любую дань при условии, что войско Кортеса не войдет в город Мехико. Тласкальцы жаловались на тяжкие поборы ацтеков, а те убеждали Кортеса, что это народ, не заслуживающий доверия, "изменники и обманщики, хотят заманить в их столицу, чтобы там вернее уничтожить". Выждав неделю, вероятнее всего, чтобы получить точную информацию о надежности своего тыла, Кортес все-таки вступил в город Тласкалу (23 сентября 1519 года), несмотря на вторичное предупреждение Монтесумы, приславшего на этот раз богатые дары.