Флотилия, вышедшая в море при столь благоприятной погоде, вскорости попала в один из тех мощных ураганов, которые нередки в Карибском море в это время года. Ее разметало во все стороны, и Кортес на своем флагманском судне «Капитанья» последним пришел к месту сбора — острову Косумель. К тому же сразу по прибытии ему пришлось заняться последствиями опрометчивых действий Педро де Альварадо, чье избыточное рвение послужило в дальнейшем причиной многих трудностей. Альварадо совершил нападение на индейский храм и похитил находившиеся в нем сокровища, что привело всю страну в полное смятение. Кортесу с помощью двух переводчиков-индейцев с трудом удалось умилостивить возмущенных туземцев.
Движимые сознанием своей миссии, сделавшим бы честь любому крестоносцу, члены экспедиции немедленно приступили к обращению индейцев-островитян в свою веру. При этом они придерживались обычного образа действия: не достигнув результатов с помощью добрых слов, переходили к насильственным методам. Индейцы были уверены в том, что дерзкие богохульники будут немедленно поражены громом и молнией, но испанцы низвергали идолов и тем самым наглядно демонстрировали индейцам бессилие их богов. Вместо идолов они сооружали христианские алтари. Затем с помощью переводчиков-индейцев, которые, очевидно, и сами толком не знали, о чем идет речь, предпринимались попытки посвятить индейцев в таинства христианской веры. Впрочем, Бартоломе Ольмедо, принимавший участие в походе в качестве духовного пастыря, был против столь скорого обращения и часто призывал командующего к разуму и терпению. В своем христианском усердии Кортес зашел настолько далеко, что даже нарушил требования дипломатического благоразумия, а это противоречило его обычно столь осмотрительной и взвешенной манере поведения.
На Юкатане удалось освободить испанца по имени Иеронимо де Агул ара, спасшегося после кораблекрушения и удерживавшегося в плену индейцами майя. После долгих томительных лет, проведенных в плену у индейского
4 марта корабли вновь подняли якоря и вскоре обогнули мыс Каточе. Благодаря попутным ветрам суда миновали Чампотун и вошли в широкий залив Кампече. Вскоре Кортес достиг устья Рио-Табаско, или Рио-Грихальва, как эта река была названа в честь ее первооткрывателя. Для того, чтобы завязать контакты с местными индейскими племенами, было решено отправиться вверх по реке, однако это было связано с определенными трудностями из-за многочисленных мелей. Высадке на берег воспрепятствовали воины, размахивавшие копьями, и ввиду позднего часа участники экспедиции предпочли отложить высадку до завтра. Уже утром испанской коннице удалось обратить противника в бегство, и отряд быстро двинулся по направлению к столице провинции Табаско, которая была взята без всякого сопротивления. Однако вскоре участники экспедиции раскаялись в том, что пустились на подобную авантюру, ибо все окрестные территории были охвачены сильным волнением, и ежечасно приходилось опасаться нападения превосходящих по численности сил противника. Также внушало опасения бегство индейца-переводчика, который мог сообщить врагу о малочисленности отряда завоевателей, а также разрушить иллюзии о сверхчеловеческой природе испанцев. Здесь нечего было ожидать, кроме потерь в живой силе и конском поголовье; золото было найдено, но в весьма незначительном количестве, далеко не соответствовавшем представлению конкистадоров.
Однако после долгих раздумий Кортес решился принять бой. Отступление в самом начале похода подорвало бы моральное состояние его людей, и тем больше возросло бы мужество индейцев.
25 марта 1519 года, в день Благовещения, члены экспедиции все вместе прослушали мессу, а затем решительно двинулись в бой. Наступление по искусственно орошаемым полям плантаций какао далось с трудом. На обширной равнине Кентла конкистадоры наконец заметили противника, всего около 40000 человек (впрочем, такого рода данные о численности вряд ли можно считать достоверными), и менее мужественные люди, чем наши испанцы, усомнились бы в победе своего оружия. Появление конницы, которой было поручено выполнение обходного маневра, задерживалось из-за непроходимости местности. Однако именно ей удалось изменить ход сражения в пользу испанцев. Индейцы, никогда еще не видевшие лошадей, в паническом страхе обратились в бегство, а всадники, возглавляемые лично Кортесом, с криками «Сантьяго!» устремились вслед за ними. На месте победы впоследствии была сооружена новая столица провинции, названная Санта-Мария-де-ла-Виктория.