За время его отсутствия Кортес неоднократно пытался обратить местных индейцев в христианство, поскольку, спасение таким образом человеческих душ рассматривалось Испанией и ее конкистадорами в качестве одной из их основных миссий. Однако жители Косумеля не только противились отказу от своих верований, но и приходили в ужас от разрушения испанцами их идолов, чем пришельцы хотели продемонстрировать беспомощность и бессилие богов, которым те поклонялись. На этот раз такие попытки вызвали только страх и недовольство островитян.
Пополнив запасы на продолжение путешествия, экспедиция оставила гостеприимный Косумель и направилась к берегу Юкатана. Но в первый же день плавания каравеллы попали в сильный шторм, и некоторые из судов так, что им всем пришлось возвращаться обратно для проведения ремонтных работ. Вскоре после выхода на берег испанцы увидели направлявшееся к ним каноэ, а когда индейцы высадились из лодки, один из них вдруг произнес на несколько неуверенном испанском: «Господа, вы христиане?» Услышав положительный ответ, этот человек бросился на колени и начал воздавать благодарственную молитву Всевышнему за свое спасение. Когда он, обливаясь слезами радости, поднялся, потрясенные этой встречей испанцы услышали от него невероятный рассказ о его приключениях.
Их соотечественника в облике индейца звали Херонимо де Агилар. Он был священником и участвовал в злополучной экспедиции Никуэсы в район Дариена у берегов сегодняшней Колумбии, в которую не попал Кортес из-за больной ноги. После неудачной попытки Никуэсы обосноваться в поселении вместе с Бальбоа в 1511 году его каравелла отправилась обратно в Санто-Доминго, но около Ямайки она попала в страшную бурю и была отнесена к побережью континента к югу от Юкатана и разбилась. На ее обломках удалось спастись всего двум десяткам людей, но 7–8 из них умерли вскоре на берегу, а остальные были захвачены индейцами. 5–6 испанцев через несколько дней были принесены в жертву местным богам, а затем съедены индейцами. Оставшихся в живых посадили в клетки. Однако на территорию племени, в плену у которого они находились, напало другое племя и увело Агилара в свои земли. Он стал рабом у вождя этого племени и подвергся многим страданиям, но затем его знания и советы были высоко оценены хозяином, который облегчил его положение и сделал его членом своего племени.
Когда посланные Кортесом индейцы передали ему письмо и он решил вернуться к своим, касике его племени стал возражать, и только принесенные щедрые дары испанцев в виде ярких стеклянных бус и других украшений решили дело в пользу его освобождения. Агилар сообщил также, что недалеко от того места, где он жил, в другом племени находился еще один испанец, который там давно женился и завел большую семью. На предложение Агилара вернуться к своим тот ответил отказом, отдав предпочтение жизни среди индейцев. Ввиду задержек в пути Агилар опоздал на ожидавшую его каравеллу и добирался с Юкатана на каноэ. Выслушав своего одичавшего соотечественника, Кортес дал ему подходящую одежду и предоставил щедрое угощение. Однако потерявший испанские привычки Агилар во всем вел себя как индеец, и ему потребовалось некоторое время, чтобы вернуться к старому образу жизни. Он провел почти восемь лет среди индейцев и за это время овладел несколькими диалектами их языка, что уже сразу оказало бесценную услугу экспедиции Кортеса.
Ремонтные работы на каравеллах были закончены, и 4 марта 1519 года Кортес повел свою флотилию вдоль Юкатана, держась как можно ближе к его берегу. Затем он прошел по маршруту де Кордоба, в некоторых точках которого его предшественнику пришлось вести ожесточенные схватки с индейцами, а потом поднялся до устья реки Табаско-Грихальва, где экспедиция последнего так успешно торговала с местными жителями. Хотя главная цель Кортеса была в посещении богатой страны ацтеков, он решил обследовать ее соседние территории и выяснить их возможности, поднявшись сначала вверх по реке к находившемуся там большому поселению.
Из-за мелкого речного устья каравеллы пришлось поставить на якоря и продолжать поход частью имевшихся сил на лодках. Появившиеся индейцы, к удивлению испанцев, проявили совершенно определенные признаки враждебного к ним отношения. Достигнув открытого пространства на сужавшихся берегах реки, отряд встретился с большим отрядом вооруженных индейцев, которые помешали Кортесу высадиться. Убедившись, что враждебность туземцев не вызывала сомнений, он высадил своих людей на небольшом острове и одновременно ниже по течению переправил на берег группу в сто солдат во главе с Алонсо де Авила. На следующее утро число собравшихся вооруженных индейцев значительно выросло, а на воде появилась масса каноэ с воинами. Кортес стал готовиться к атаке, которая стала первым его боем с индейцами континента.
Несколько каноэ направились к острову испанцев и, приблизившись, через переводчика Агилара предложили им небольшое количество продуктов за обещание покинуть их землю. Кортес настаивал на своих мирных намерениях и желании посетить их город, прося встречи с касике. Недовольные индейцы обещали подумать и вернуться с ответом, но слово не сдержали, а когда к вечеру испанцы попытались получить его от них, их просьба была встречена презрительным смехом и угрозами. После этого отряд Кортеса направился на бригантине к берегу индейцев и вступил с ними в бой. Противник оказал ожесточенное сопротивление, но выстрелы пушек и огнестрельного оружия, с которыми оборонявшиеся столкнулись впервые, обеспечили их отступление в сторону главного поселения Потончан, а после вступления в бой прибывшего по сигналу отряда Авила индейцы растворились в ближайших лесных зарослях. Испанцы вошли в город и расположились в огромном каменном храме, который мог служить хорошей крепостью на случай обороны.
Несмотря на большое сражение, Кортес хотел по-прежнему мирно договориться с табасканами, прежде всего, о получении необходимого провианта. В этих целях он отпустил захваченных в плен и раненых индейцев, заверил их в своих мирных планах и снова просил встретиться с касике. На следующий день перед испанцами появилось двадцать послов с некоторым количеством продуктов и заверениями, что большего они дать не могут, а касике находится очень далеко, но снова обещали дать ответ на другой день.
Кортес начинал понимать, что индейцы пытаются его обмануть, и направил три отряда на поиск кукурузных полей и дичи, которые скоро обнаружили эти поля, но они находились под плотной защитой массы вооруженных туземцев, не желавших обменивать кукурузу на европейские изделия. Завязалась новая схватка, в которой было ранено много испанцев, нашедших при отступлении большой дом, где они отбивались от окруживших их индейцев. Положение спас Кортес со своей группой солдат благодаря привезенным двум пушкам, что и решило на время исход кровавого боя, в котором погибло немало индейцев. На следующий день глава экспедиции вывел свои основные силы в составе 500 человек с конницей и артиллерией на боевые позиции. Его главный пехотный отряд столкнулся с многотысячным войском неприятеля на том же самом огромном поле, где состоялась вчерашняя битва. И снова вспыхнул бой при невероятном численном преимуществе туземцев, что довольно скоро поставило испанцев в очень опасное положение, поскольку они оказались зажатыми в одном углу и с трудом отбивались. Кортес предусмотрительно скрытно расположил конницу в тылу врага и в решающий момент выпустил ее на противника. Индейцы, никогда не видевшие лошадей, приняли их за страшных чудовищ, считая их вместе со всадниками одним невероятным существом, и в панике покинули поля боя, ища спасения в ближайших зарослях. Преследовавшая их пехота уничтожила свыше 300 человек и многих ранила.
После таких тяжелых побоищ Кортес, возможно, уже сожалел, что ввязался в эту историю в самом начале своего похода в страну ацтеков, но теперь ему было необходимо доказать непобедимость испанцев даже перед лицом гораздо более многочисленного противника, что было важно для восприятия могущества его отряда в глазах других племен. Он снова отпустил раненых индейцев с посланиями к их вождям, сообщая, что они понесли наказание за ложь, обман и насилие, которые они проявили по отношению к испанцам, но обещал простить их и заверил в своей дружбе, если они были к этому готовы. К назначенному сроку делегация вождей в сопровождении большой толпы индейцев явилась на встречу с Кортесом, принеся с собой много разного продовольствия и приведя даже рабов для работы на испанцев. Они просили прощения за свое прошлое поведение и заверили победителей в том, что они теперь стали их друзьями и будут безвозмездно снабжать и обслуживать их. Кроме того, они согласились принять верховную власть испанского монарха.
