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