Через несколько дней местные вожди прислали припасы и привели двадцать молодых женщин. Кортес приказал их немедленно окрестить, а затем распределил "первых христианок Новой Испании" между своими командирами. Одну из них, прославленную испанскими хронистами донью Марину, "самую красивую, разумную и расторопную", Кортес сначала отдал знатному офицеру, а когда тот уехал в Испанию, взял к себе. Она стала переводчицей и советницей Кортеса и оказала огромные услуги испанцам в первые годы завоевания Мексики. Марина указывала Кортесу, на какие народности он может опираться в борьбе против их поработителей - верховных вождей ацтеков. Уроженка переходной области, перешейка Теуантепек, она одинаково свободно владела языками ацтеков и майя ("юкатанским").

Оставив Табаско, флотилия Кортеса после трехдневного безостановочного перехода подошла к острову Сан-Хуан-де-Улуа и встала на якорь между ним и материком (21 апреля 1519 года).

Пришельцев приветствовали посланцы Монтесумы, которому доносили о движении флотилии. На следующий день испанцы высадились на берег материка, выгрузили лошадей и пушки и разместили их на высоких песчаных холмах. Для командиров были построены укрытые бараки, а солдаты поставили для себя шалаши, сплетенные из ветвей. В дальнейшем им во всем помогали мексиканцы, которые доставляли в изобилии провизию, но только для командиров. Через два дня к Кортесу прибыл с большой свитой правитель приморской области с другим сановником. Послы передали ему богатые дары от Монтесумы: "множество драгоценностей... из прекрасного золота и чудесной работы... десять тюков белоснежной хлопчатобумажной ткани, изумительные изделия из птичьих перьев и много еще других ценных вещей..." Кортес одарил послов и свиту бусами, а для самого Монтесумы передал более ценные дары.

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

Так как стоянка для кораблей у Сан-Хуан-де-Улуа оказалась очень ненадежной, а место для лагеря было выбрано неудачно, Кортес отправил на север на разведку два корабля под командой Франсиско Монтехо и Антона Аламиноса. Те дошли до реки Пануко, но безопасную гавань и более удобное место для военного городка нашли лишь недалеко от старого лагеря.

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

Сторонники Веласкеса из числа идальго, обеспеченных поместьями на Кубе, настаивали на возвращении на остров, пугая опасностями солдат. Кортес сделал вид, что подчиняется, а сам инсценировал бунт... против себя. "Бунтовщики" потребовали, чтобы никто не уходил на Кубу, объявили Кортеса главным судьей и генерал-капитаном, независимым от Веласкеса, который к тому времени был официально назначен наместником короля. Кортес "против своей воли" подчинился, а наиболее ревностных сторонников Веласкеса на несколько дней посадил на цепь. Среди них был Диего Ордас, который, как и другие, в собственных интересах вскоре стал горячим защитником Кортеса.

Чтобы обеспечить свой тыл при движении внутрь страны, испанцы построили город Веракрус.