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

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

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

В устье следующей крупной реки, Папалоапана, Педро де Альварадо, человек отчаянный и бесшабашный, ввел свой корабль в одиночку, вопреки приказам Грихальвы; после этого все четыре судна держались вместе, пока не достигли реки Хамапа. Это место находится немного не доходя до современного города Веракрус, а чуть к северу от реки имеется хорошее укрытие для кораблей между отмелей под Пунто-Мокамбо. Здесь индейцы буквально приветствовали испанцев, и Грихальва сошел на берег, разговаривал с касиками и выменял украшений из золота низкой пробы на 16 000 песо. Именно здесь он наконец именем Веласкеса объявил эту страну владением испанской короны.

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