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