Мигель был доволен условиями своей службы. До начала экспедиции его определили жить в казарму. Ожидая окончательного решения губернатора, Кортес успел набрать отряд из 300 человек. Кроме того, Кортесу удалось собрать неплохой арсенал. Для солдат были заказаны стеганые куртки. Кортес купил каравеллу и бригантину, к которым добавился корабль Алварадо. Вскоре удалось найти еще четыре корабля.
Тем временем Грихалва вернулся из Веракруса. Отчет Грихалвы показал, что Алварадо в наглую оклеветал своего командира. У Веласкеса теперь появились серьезные сомнения относительно кандидатуры Кортеса. Кортес быстро понял изменение ситуации и решил не ждать, а действовать. Веласкес узнал о том, что Кортес отплывает только от своего мясника, так как Кортес погрузил на корабли двухнедельный запас мяса. «Ты уже отплываешь?» – спросил Веласкес Кортеса, стоявшего уже в шлюпке. Кортес в ответ крикнул, что все идет по плану и тут же приказал своим людям отплывать.
Но, несмотря на все приготовления, экспедиция Кортеса испытывала нехватку в провизии и людях. Кортес остановился у Пилона и погрузил на корабли 1000 хлебов-кассава, получив его у друзей-плантаторов. Затем он отправил один из своих кораблей к Ямайке, где получил 800 полутуш и еще 2000 хлебов. Далее Кортес прибыл в Тринидад, но туда уже дошел приказ о его аресте, поэтому магистрат разговаривать с Кортесом не стал. Тогда Кортес воспользовался оговорками в контракте и взял все командование экспедицией на себя. Один из офицеров по имени Ордас взял на абордаж проходящее мимо судно, груженное припасами, направляющееся в колонию Дариен в Панаме. В Тринидаде к экспедиции присоединились еще две сотни человек, в основном это были только что вернувшиеся участники экспедиции Грихалвы.
Вскоре Кортесу удалось договориться с членами магистрата Тринидада, пообещав тем долю от предстоящих прибылей. Заручившись их поддержкой, Кортес получил несколько лошадей. Лошадей в Новом Свете было очень мало. Это были потомки животных, завезенных сюда еще Колумбом. Каждый конь стоил порядка трех тысяч песо. Это были невысокие, но выносливые животные, которые могли нести воина в доспехах, сидящего в высоком мавританском седле. Кроме того, Кортес закупил некоторое количество собак: волкодавов и мастиффов. Как показала практика, свора таких собак была очень эффективным средством от индейской легкой пехоты. Наконец, Кортесу удалось заполучить большую партию стеклянных бус, колокольчиков, зеркал, иголок и булавок, а также железных ножей, ножниц, щипцов, молотков и топоров. Эти обычные для Европы товары были совершенно неизвестны в Америке и поэтому пользовались бешеным спросом. Среди мексиканских индейцев основным способом социального обмена было дарение. Стекла индейцы не знали вообще, поэтому бусы для них казались бесценными вещами. Владение такими бусами означало, что человек имеет необычных торговых партнеров. Хотя металлургия в Америке развивалась с X века, она была сконцентрирована в руках императорского двора, при этом индейцы умели обрабатывать только золото, серебро и медь. Железные предметы также вызывали у индейцев удивление и восторг.
К февралю 1519 года удалось набрать достаточно воды, хлеба, копченого мяса, соли, масла, уксуса и вина, чтобы прокормить 500 участников экспедиции на протяжении нескольких недель, в течение которых будет происходить разведка побережья Юкатана до Веракрус. В дальнейшем планировалось перейти к самостоятельному снабжению. Ветераны прежней экспедиции рекомендовали взять с собой как можно больше бочек для воды, так как поведение индейцев часто было непредсказуемым и никогда нельзя было быть уверенным в том, что на берегу удастся что-нибудь получить. Кортес внял предостережениям, потому что ему очень не хотелось, чтобы его люди голодали или страдали от жажды, как это случилось в ходе экспедиции Кордовы и Грахалвы.
Несмотря на то, что корабли уже в первую ночь потеряли друг друга, все кроме одного успешно преодолели 50 миль, разделявших Кубу и Юкатан. Высадившись у Косумеля, испанцы встретили радушный прием со стороны местных индейцев-майя. Спустя десять дней к ним присоединился Херонимо де Агилар, который потерпел кораблекрушение здесь десятью годами раньше. Агилар провел эти годы рабом у местного вождя, поэтому научился свободно разговаривать на индейском языке.
Далее корабли двинулись на запад вдоль побережья, мимо острова Исла-де Мухарес к мысу Каточе. При любой возможности Кортес пополнял запасы еды и воды. Наконец, экспедицию догнал последний отставший корабль. Эта встреча произошла в бухте Кампече, неподалеку от того места, где Грихалва потерпел поражение от майя. Кортес думал провести карательную акцию, но в итоге решил направиться в Табаско, где его армия высадилась на берег и двинулась вглубь материка в направлении Потончана – торгового города индейцев-майя. Там они напали на отряд майя, который отступил и соединился с союзниками. В последовавшем сражении при Сентле многие испанцы получили ранения, но не потеряли ни одного человека. Потери индейцев достигли 800 человек, прежде чем туземцы поняли бесперспективность дальнейшего боя и отступили. Возвращаясь в Потончан, Кортес принял дань, которую предоставил ему местный правитель. Затем Кортес допросил взятых пленных на предмет нахождения источников золота. Вскоре стало ясно, что источники золота находятся в глубине материка, на западе. Там находились земли, которыми правил император ацтеков из столицы Теночтитлан. Агилар не знал ацтекского языка, но нашлась женщина по имени Млинцин, которая уверила Кортеса, что знает как наречие ацтеков, так и майя. «Донна Марина», как ее называли испанцы, и Агилар образовали ядро дипломатического корпуса, который сыграл значительную роль в дальнейшем. Основываясь на данных, полученных через переводчиков, Кортес принял решение начать войну с Монтенсумой.
