Движимые сознанием своей миссии, сделавшим бы честь любому крестоносцу, члены экспедиции немедленно приступили к обращению индейцев-островитян в свою веру. При этом они придерживались обычного образа действия: не достигнув результатов с помощью добрых слов, переходили к насильственным методам. Индейцы были уверены в том, что дерзкие богохульники будут немедленно поражены громом и молнией, но испанцы низвергали идолов и тем самым наглядно демонстрировали индейцам бессилие их богов. Вместо идолов они сооружали христианские алтари. Затем с помощью переводчиков-индейцев, которые, очевидно, и сами толком не знали, о чем идет речь, предпринимались попытки посвятить индейцев в таинства христианской веры. Впрочем, Бартоломе Ольмедо, принимавший участие в походе в качестве духовного пастыря, был против столь скорого обращения и часто призывал командующего к разуму и терпению. В своем христианском усердии Кортес зашел настолько далеко, что даже нарушил требования дипломатического благоразумия, а это противоречило его обычно столь осмотрительной и взвешенной манере поведения.

На Юкатане удалось освободить испанца по имени Иеронимо де Агул ара, спасшегося после кораблекрушения и удерживавшегося в плену индейцами майя. После долгих томительных лет, проведенных в плену у индейского касика, в постоянном страхе быть принесенным в жертву, спасение показалось испанцу чудом. Это было удачей и для Кортеса, поскольку Агул ар научился языку майя, так что впоследствии экспедиция не зависела от услуг ненадежных переводчиков-индейцев.

4 марта корабли вновь подняли якоря и вскоре обогнули мыс Каточе. Благодаря попутным ветрам суда миновали Чампотун и вошли в широкий залив Кампече. Вскоре Кортес достиг устья Рио-Табаско, или Рио-Грихальва, как эта река была названа в честь ее первооткрывателя. Для того, чтобы завязать контакты с местными индейскими племенами, было решено отправиться вверх по реке, однако это было связано с определенными трудностями из-за многочисленных мелей. Высадке на берег воспрепятствовали воины, размахивавшие копьями, и ввиду позднего часа участники экспедиции предпочли отложить высадку до завтра. Уже утром испанской коннице удалось обратить противника в бегство, и отряд быстро двинулся по направлению к столице провинции Табаско, которая была взята без всякого сопротивления. Однако вскоре участники экспедиции раскаялись в том, что пустились на подобную авантюру, ибо все окрестные территории были охвачены сильным волнением, и ежечасно приходилось опасаться нападения превосходящих по численности сил противника. Также внушало опасения бегство индейца-переводчика, который мог сообщить врагу о малочисленности отряда завоевателей, а также разрушить иллюзии о сверхчеловеческой природе испанцев. Здесь нечего было ожидать, кроме потерь в живой силе и конском поголовье; золото было найдено, но в весьма незначительном количестве, далеко не соответствовавшем представлению конкистадоров.

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

25 марта 1519 года, в день Благовещения, члены экспедиции все вместе прослушали мессу, а затем решительно двинулись в бой. Наступление по искусственно орошаемым полям плантаций какао далось с трудом. На обширной равнине Кентла конкистадоры наконец заметили противника, всего около 40000 человек (впрочем, такого рода данные о численности вряд ли можно считать достоверными), и менее мужественные люди, чем наши испанцы, усомнились бы в победе своего оружия. Появление конницы, которой было поручено выполнение обходного маневра, задерживалось из-за непроходимости местности. Однако именно ей удалось изменить ход сражения в пользу испанцев. Индейцы, никогда еще не видевшие лошадей, в паническом страхе обратились в бегство, а всадники, возглавляемые лично Кортесом, с криками «Сантьяго!» устремились вслед за ними. На месте победы впоследствии была сооружена новая столица провинции, названная Санта-Мария-де-ла-Виктория.

Радость победы была тем оправданнее, что потери испанцев оказались незначительными. Жители Табаско были настолько деморализованы своим поражением (ведь они потеряли несколько тысяч человек), что покаянно молили победителя о пощаде и заключили с испанцами мир. В знак примирения вожди преподнесли подарки, и в их числе 20 индейских девушек, которых Кортес после крещения распределил среди своих капитанов. Среди них была Малицин, в испанском произношении Малинхе, получившая после крещения имя Марина. Она была дочерью князя из области, где говорили на языке науатл, в состав которого входил и язык ацтеков. Агулар, переводчик испанцев, выучил на Юкатане язык майя, но язык ацтеков, науатл, был ему незнаком. Однако дочь индейского вождя могла переводить речи туземцев с языка науатл на язык майя, а Агулар затем переводил их на испанский.

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

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

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

В святой четверг 1519 года, в полдень, испанцы достигли Сан-Хуан-де-Улуа, и корабли встали на якорь. К радости испанцев, индейцы этой страны встретили их мирно. Они находились в стране тотонаков — племени, которое не так давно стало вассалом ацтеков. К флагманскому кораблю испанцев, «Капитанье», подошли две пироги, и гребцы заявили, что хотят видеть предводителя белых людей. Кортес пригласил послов на борт, где встретил их самым любезным образом — яствами и напитками. Затем он расспросил их с помощью доньи Марины и Агулара и, наградив богатыми подарками, отправил обратно.

В последующие дни появлялись и другие делегации индейских послов, привозившие в подарок провизию и украшения из золота. В пасхальное воскресенье явился даже важный индейский вельможа. Это был наместник Монтесумы на прибрежных территориях, которого сопровождали другие вожди и множество носильщиков. Кортес приветствовал послов от имени испанского монарха и пригласил их принять участие в начинавшейся как раз в тот момент пасхальной мессе. Затем произошел обмен подарками. Испанцы получили 20 комьев хлопка, изделия из перьев — особое индейское искусство — и золотые украшения; в качестве ответного подарка Кортес вручил резное кресло, украшенную золотой монетой красную шапку, бусы и горный хрусталь. В дополнение к этому он заявил, что надеется вскорости лично встретиться с властителем Мексики. Наместник имел при себе нескольких искусных рисовальщиков, которые с точностью переносили на бумагу все впечатления, полученные в лагере испанцев, чтобы представить властителю ацтеков живописный портрет страшных «бледнолицых».