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

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

Даже миссионерская деятельность среди индейцев давала ощутимые плоды. Некоторых индейских вельмож удалось подвигнуть на перемену веры, доказав им бессилие местных богов проверенным способом — сбросив их с постаментов. Было также заключено несколько браков между дочерьми индейских вождей и бледнолицыми; испанцам вообще незнакомо было чувство расового превосходства. Для того чтобы еще прочнее привязать к себе тотонаков, Кортес приказал им захватить пятерых мексиканских сборщиков налогов. При этом он вел двойную игру, поскольку приказал испанцам тайно освободить ацтекских чиновников и отправил их обратно к Монтесуме с дружественным посланием. Посредством такого ловкого хода, который следует признать проявлением коварства, он, с одной стороны, навсегда оставил тотонаков под своими знаменами, ибо Монтесума никогда не простил бы тем нанесенного оскорбления, с другой же стороны, мог претендовать на благодарность мексиканцев, которые не подозревали об истинном положении вещей.

Этим Кортес проявил себя как истинный сын своего времени, поскольку ради интересов своих и своего властителя пренебрег любыми сомнениями морального характера — ведь шесть лет назад была написана книга Макиавелли о государе.

В Семпоалле Кортес также написал доклад молодому королю. Это было первое из знаменитых пяти писем «Cartas de Relation», которые, впрочем, впоследствии волею несчастного случая были утрачены, и в настоящее время их больше не существует; воспоминания Берналя Диаса представляют собой их несовершенную замену. Необходимо было обеспечить себе защиту от возможных санкций со стороны кубинского наместника, и Кортес знал, что противостоять интригам и проискам клики при испанском дворе ему удастся только с помощью золота. Так, он отказался от полагавшейся ему пятой части всей завоеванной до тех пор добычи и сумел уговорить своих солдат отказаться от своей доли.

В июле 1519 года лучший корабль эскадры при попутном ветре отплыл в Испанию. Капитаны Пуэртокарреро и Монтехо, которым было доверено столь важное предприятие, нарушив категорический приказ генерал-капитана, зашли на остров Кубу, так что о судьбе экспедиции стало известно губернатору Веласкесу. Это были первые сведения, полученные со дня отплытия флотилии. Несмотря на то, что Веласкес пытался перехватить корабль, капитанам удалось своевременно ускользнуть и после благополучного перехода через океан прибыть в Сан-Лукар. Здесь всесильный епископ Бургоса, Хуан Родригес де Фонсека, который со времен второго путешествия Колумба был председателем совета по делам Индии, сумел поставить на пути посланников Кортеса одну за другой всякого рода сложности. Ему удалось препятствовать их аудиенции у короля Карла до тех пор, пока в Испанию не прибыло сообщение от его протеже и родственника Веласкеса, в котором тот выдвигал самые резкие обвинения против Кортеса. Теперь предстояло рассмотреть доклады, опровергающие друг друга. Кортес, считавший Фонсеку своим явным врагом, прекрасно знал, что для устранения влияния епископа необходимы большие деньги. Отцу завоевателя, дону Мартину Кортесу, удалось с помощью ловкого адвоката добиться выдачи драгоценностей из золота. Вскоре выяснилось также, что король не станет вешать того, кто может предложить столь роскошные подарки. Здесь пригодился опыт, полученный Кортесом в период службы в качестве чиновника на Кубе. Ведь он хорошо разбирался в обстановке, сложившейся при дворе, и знал, кого можно расположить в свою пользу при помощи подкупа. С помощью богатых подарков королевским фаворитам и прежде всего секретарю Кобосу удалось нейтрализовать интриги епископа Бургоса.

Для Эрнана Кортеса прием его посланников при дворе был полным успехом. Король выразил свою благодарности и вместе с придворными восхищался драгоценными произведениями искусства незнакомого им мира. Удивление вызывали также четыре индейца и две индианки, которые в роли первых посланников Мексики ступили на европейскую землю. В золоте Кортес обрел самого горячего своего заступника, ведь при дворе, где потребность властителя в капиталах все возрастала и финансовое положение становилось все более напряженным, оно считалось наиболее убедительным аргументом. Король узаконил деятельность конкистадора и одобрил самоуправное провозглашение Веракруса; одновременно он отдал распоряжение снарядить три корабля для оказания поддержки Кортесу. Впрочем, окончательное урегулирование мексиканских дел несколько затянулось из-за отъезда Карла в Германию.

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

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

16 августа 1519 года небольшая армия бледнолицых завоевателей в сопровождении союзников-тотонаков выступила в направлении столицы мексиканской империи. В первый день путь лежал по Tierra caliente («Горячая земля»), той чрезвычайно красивой и плодородной местности, где они провели столь долгое время, будучи гостями тотонаков. Через несколько миль пути отряд добрался до крутых склонов Кордильер, где был разбит первый лагерь. К концу второго дня пути испанцы достигли города Халапа; позади осталась зона влияния Tierra caliente и коварная местность, зараженная малярией.

Далее путь лежал через теснины Пасо-дель-Обиско, сурового перевала, где испанцы после долгого перерыва снова увидели снег и лед. Тотонаки, жители теплой прибрежной местности, особенно страдали от непривычного для них холода. Двигаясь вдоль северных склонов Кофре-де-Пероте, отряд прошел через перевал Съера-дель-Агуа и наконец добрался до горного плато, высота которого превышала 2400 м. Здесь снова царил приемлемый климат и были видны следы оживленной хозяйственной деятельности. Плантации кукурузы и агавы с пышными желтыми гроздьями цветов на высоких стволах указывали на близость крупного поселения.