В 1517 г. солдаты, слонявшиеся без дела на Кубе, составили отряд, выбрали богатого капитана, Франсиско Эрнандеса Кордову, решили испытать счастье и отправиться на поиски новых земель. Но главная задача экспедиции заключалась в захвате рабов для пополнения истощившихся ресурсов «рабсилы» на Кубе. Среди солдат был Берналь Диас дель Кастильо, автор «Правдивой повести о завоевании Новой Испании». (Цитаты ниже взяты из его книги.) Они приобрели и снарядили на свои средства два больших корабля, наняли матросов и трех штурманов; старший — Антон Аламинос. Третье судно дал в долг наместник Кубы Диего Веласкес, снабдив экспедицию провиантом; на свои деньги солдаты купили еще свиней и запаслись всякими безделушками для обмена. Они вышли из Гаваны 8 февраля 1517 г. и четыре дня шли вдоль берега Кубы, а затем в открытом море, двигаясь наугад на запад. Шторм свирепствовал двое суток, и корабли едва не погибли. Когда буря стихла, Аламинос переменил курс, но только в начале марта показалась земля — северо-восточный берег п-ова Юкатан. Вдали, близ мыса, видно было большое селение.

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

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

Испанцы вернулись на суда и пошли дальше, двигаясь только днем; ночью останавливались, но нигде не высаживались. Суда прошли на запад вдоль северного плоского берега несколько сот километров. Затем он круто повернул на юг, и Аламинос решил, что открытая земля — остров. После двухнедельного плавания вдоль его берегов испанцы увидели вдали селение. Пресной воды оставалось очень мало, и они подошли к берегу страны Кампече, чтобы набрать воды. К кораблям прибыла группа индейцев «в хорошей одежде из хлопчатобумажных тканей». Они руками указывали на восток — не оттуда ли пришли испанцы, повторяя слова «кастилан» (т. е. кастильцы). Они привели солдат к большим домам, очень хорошей каменной кладки. «То были храмы их идолов с изображениями больших змей и других чудовищных идолов на стенах. Внутри было нечто вроде алтаря, покрытого запекшейся кровью». Какие-то люди в разодранных плащах принесли вязанки сухого тростника и сложили их в кучу; прибыли два отряда стрелков и пращников в ватных панцирях, со щитами и копьями, и остановились поблизости. «…Из соседнего… храма вышли десять индейцев в длинных — до пят — белых плащах. Их длинные волосы были так перепутаны и загрязнены запекшейся кровью, что их нельзя было расчесать — разве только срезать. Это были служители идолов… они окружили нас… и знаками дали понять, что мы должны покинуть их страну раньше, чем сгорит тростник… не то нас атакуют и перебьют. Затем они велели зажечь кучу и смолкли. А воины, построившись в боевом порядке, стали свистеть, трубить в трубы и бить в барабаны… И на нас напал такой страх, что мы сомкнутым строем отступили к берегу… и отплыли».

Корабли двинулись дальше на юг, держась ближе к земле, чтобы запастись свежей водой, пока через две с лишним недели не увидели речку и небольшое селение Чампотон. Солдаты во главе с Кордовой отправились за водой в лодках. Утром на них напали индейцы — после часовой битвы испанцы потеряли более 50 человек убитыми, пять утонуло, а двое попало в плен. Кордова, получивший 10 ран, истекал кровью. Бросив бочки с водой, испанцы вернулись на корабли.

Для управления ими не хватало рук — почти все были ранены, поэтому одно судно пришлось сжечь. В поисках пресной воды моряки пошли на юго-запад и на третий день заметили бухту, в которую впадала речка, но вода там оказалась горько-соленой. Эту бухту у юго-западной окраины Юкатана Аламинос позднее назвал лагуной Терминос, так как все еще надеялся найти там конец (по-испански «терминов) мнимого «острова». Но берег оттуда поворачивал к западу, и томимые жаждой испанцы решили идти обратно — к Кубе.

Несмотря на несчастья, экспедиция обследовала весь северный и западный берега Юкатана на протяжении 700 км и открыла страну народа майя, стоявшего на гораздо более высокой ступени культуры, чем индейские племена, уже знакомые европейцам. Чтобы ускорить путь, Аламинос предложил возвращаться не вдоль берегов Юкатана — в этом случае пришлось бы все время идти против ветра и течения, а воспользоваться течением Гольфстрим и плыть к Флориде. Испанцы пересекли Мексиканский залив и достигли западного берега Флориды, пройдя больше 1200 км за четыре дня. Выдержав на берегу стычку с индейцами, но все же забрав воду, неудачные конкистадоры вернулись на Кубу. Кордова умер через 10 дней после возвращения.

Несмотря на разгром испанцев, золотые изделия, привезенные из Юкатана, так воспламенили воображение искателей приключений, что уже в 1518 г. была организована на Кубе новая, более сильная экспедиция во главе с Хуаном Грихальвой. В его распоряжении находилось четыре корабля (из них два снарядил Веласкес) и отряд в 240 солдат. Старшим штурманом был тот же Аламинос, а участником экспедиции — Б. Диас. Педро Альварадо (позже спутник Кортеса) командовал одним из кораблей.

Флотилия, отплыв 8 апреля 1518 г., шла на запад путем Кордовы, но течением ее отнесло к югу. При этом был открыт о. Косумель у восточного берега Юкатана. Не задерживаясь здесь, испанцы двинулись дальше: Грихальва спешил отомстить жителям Чампотона и высадил на берег отряд. Индейцы уже ожидали испанцев и при высадке ранили многих солдат, но, показавшись на берегу и надев ватные панцири, испанцы опрокинули индейцев, потеряв семь человек, раненых было 60, в том числе и Грихальва. После таких потерь они решили вести себя миролюбиво.

От лагуны Терминос корабли осторожно шли на запад вдоль берега, и только через несколько суток достигли устья большой р. Табаско (р. Грихальва). На берегу появились толпы людей. Со всех сторон, из лесу слышался шум падающих деревьев: то индейцы устраивали засеки. Все-таки испанцы высадились на берег. Вскоре к ним направилось множество лодок с воинами; Грихальва через пленных приказал передать вождям, чтобы они без опаски пришли для переговоров. Обе стороны обменялись подарками. Индейцы прислали съестные припасы, разложили на земле несколько плащей и художественно выполненных изделий из низкопробного золота, говоря, что больше золота у них нет, зато на западе есть страна, где очень его много, и при этом несколько раз повторили слово «Мехико». Испанцы немедленно двинулись дальше, чтобы отыскать эту страну. Берег поворачивал к северо-западу; вдали виднелись снежные горы. Близ устья одной реки испанцы увидели толпу индейцев, на длинных копьях которых развевались белые флаги. То были посланцы верховного вождя ацтеков Монтесумы (правильнее астеки и Монтекухсома Шокойоцин) — повелителя Мексики. Он знал о событиях у берегов Юкатана, о дальнейшем пути чужеземцев к северу, о том, что они ищут золото, и приказал жителям давать золотые вещи в обмен на заморские «товары», чтобы узнать, куда и зачем идут кастильцы. Из всех окрестных поселений стали приносить золотые украшения, сделанные довольно грубо из низкопробного золота, но в количествах, еще не виданных конкистадорами. Испанцы продолжали путь и вскоре открыли небольшой архипелаг. На одном острове они нашли каменные строения, где по ступеням можно было подняться к алтарям. «На этих алтарях стояли отвратительные идолы. То были индейские боги. И не далее как ночью им принесли в жертву пять индейцев; тела их, растерзанные, с вскрытой грудью и обрубленными руками и ногами, валялись еще здесь; стены были залиты кровью». Высадившись на песчаный берег, испанцы построили жилища на вершинах дюн, так как внизу нельзя было спастись от москитов. Недалеко в море лежал о. Сан-Хуан-де-Улуа. Там нашли храм и в нем четырех индейцев-жрецов в черных плащах. «В этот день они принесли в жертву двух мальчиков, рассекли им грудь и положили их окровавленные сердца в дар своему пакостному богу. Хотели они нас окурить, но мы не дались. Очень уж потряс нас вид так жестоко зарезанных мальчиков».