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

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

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

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

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

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

В июле 1519 года лучший корабль эскадры при попутном ветре отплыл в Испанию. Для Эрнана Кортеса прием его посланников при дворе оказался триумфальным. Король выразил свою благодарность и вместе с придворными восхищался произведениями искусства Нового Света. Король узаконил деятельность конкистадора; одновременно он отдал распоряжение снарядить три корабля в помощь Кортесу.

16 августа 1519 года испанские завоеватели вместе с тотонаками выступили в направлении мексиканской столицы Теночтитлана. У крутых склонов Кордильер был разбит лагерь.

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

Преодолев перевал, конкистадоры вступили на земли враждебно настроенных племен. Как сообщает Берналь Диас, первое столкновение с главными силами тласкаланцев произошло 2 сентября 1519 года, а через три дня разыгралось еще одно крупное сражение. Кортес утверждал в своих письмах королю, что индейцев было 139 тысяч. Битва происходила на равнине, где и конница, и артиллерия могли развернуться.