Большое количество крупных каменных крестов, которое они встречали во многих местах, напомнило путешественникам об их далекой родине, и Грихальва назвал эти земли «Новая Испания». Первая дружественная встреча с местными жителями и выгодный товарообмен ждали испанцев в устье реки Табаско, которую руководитель экспедиции назвал в честь самого себя и которая до сих пор называется рекой Грихальва. Последующие встречи с обитателями новых земель были еще более обнадеживающими как с точки зрения их расположения к испанцам, так и в отношении ведения очень выгодного для них обмена товарами. Теперь путешественники находились уже на территории собственно империи ацтеков. Они сами об этом еще не знали, но сведения об их появлении уже поступили в ее столицу в глубине континента.
Следуя дальше вдоль берега, экспедиция достигла места, названного ими Сан-Хуан-де-Улуа, где Грихальва вступил во владение новым открытым краем от имени Веласкеса в пользу короля. Здесь многие члены экипажа, охваченные жаждой столь близко лежавшего богатства, уговаривали и умоляли Грихальву основать на этом месте колонию, в которой они мечтали остаться, но безвольный руководитель экспедиции решил слепо следовать указаниям своего дяди-губернатора, которые предусматривали только ведение торговли. Плавание Грихальвы продолжалось уже пять месяцев, и потерявший терпение из-за отсутствия о нем новостей Веласкес отправляет на его поиски в район Юкатана каравеллу под командованием Кристобаля де Олида. После его отплытия в Сантьяго прибыл с огромным ценным грузом Педро де Альварадо, который оставил группу задерживавшегося с возвращением Грихальвы. Рассказы Альварадо о несметных богатствах новых земель, подтверждением чего служили привезенные им ценности, привели Веласкеса и всех испанцев острова в неописуемый восторг. Отказ же Грихальвы основать колонию в тех местах вызвал у губернатора настоящий приступ ярости, и когда тот через некоторое время вернулся в Сантьяго с докладом, он отказался даже его принять. Олид, потерявший якорь на пути в Юкатан, довольно быстро вернулся на Кубу, где Веласкес уже спешно занимался подготовкой новой экспедиции по следам Грихальвы.
Диего Веласкес был состоятельным, но очень жадным человеком и стремился организовывать собственные экспедиции за чужой счет, как, впрочем, это было и в случае с походом Грихальвы, который был оплачен деньгами ряда самих ее участников или других богатых людей. На этот раз он предложил покрыть расходы экспедиции Бальтасару Бермудесу, с которого запросил огромную сумму за поставку оружия и провианта, и тот решительно отказался, несмотря на настоятельные уговоры губернатора Тогда Веласкес обратился со своим предложением к Эрнану Кортесу, с которым он был готов разделить все расходы пополам.
