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