Неоправданное уничтожение двух цивилизаций, полное разграбление их владений и порабощение их народов не удовлетворило испанцев. Там, где существовало две цивилизации, могли быть и другие, и каждый испанский искатель приключений стремился повторить подвиги Кортеса и Писарро. Все берега и большая часть внутренних областей тропический зоны Америки теперь были заблокированы, и местом поисков нового золота стала самая большая область неисследованной земли, которая до сих пор существовала, район к северу от Мексики.
Первым из тех, кто отправился искать золото на севере, был Панфило де Нарваэс. Он служил вместе с Веласкесом во время завоевания Кубы, и Веласкес послал его в Мексику, когда стало казаться, что Кортес становится слишком могущественным. Кортес нанес поражение Нарваэсу в Мексике, и тот стремился завоевать собственные лавры в другом направлении.
В 1528 году, после открытия Флориды Понсе де Леоном, он исследовал северную часть побережья Мексиканского залива к западу от этого полуострова. От нынешней Пенсаколы он отправился в глубь материка в поисках такой же цивилизации и золота, какие недавно нашли в Мексике. Но разочаровался и вынужден был вернуться обратно на побережье. Там он построил пять кораблей и попытался переплыть Мексиканский залив, но погиб во время шторма.
Часть его экспедиции, однако, под предводительством Альвара Нуньеса Кабеса де Ваки, его заместителя, пережила этот шторм и потерпела крушение на северной части побережья Мексиканского залива, в нынешнем Техасе. Кабеса де Вака попал в плен к индейцам на шесть лег, но в конце концов убежал, пешком пересек Северную Мексику и добрался обратно к Мехико-Сити в 1536 году.
После возвращения Кабеса де Вака рассказывал красочные истории о своих приключениях, описывал обширные стада буйволов и пересказывал слухи об огромных богатствах где-то на севере. Эти рассказы дошли до Эрнандо де Сото, который был заместителем Писарро во время завоевания Перу и который теперь жил в отставке в Испании. Читая о приключениях Кабеса де Ваки, де Сото захотел возглавить экспедицию на север Флориды, чтобы найти там еще одну такую золотую страну, как Перу.
Получив разрешение от Карла I, де Сото высадился на западном побережье Флориды (недалеко от нынешней Тампы) 25 мая 1539 года. Во главе отряда из 500 человек и 200 лошадей он отправился в глубь суши и прошел через леса нынешних юго-восточных штатов США.
Где-то в районе нынешней юго-западной части Алабамы он вступил в битву с индейцами, в которой он и большинство его людей были ранены. Это была первая битва индейцев с европейцами на территории нынешних Соединенных Штатов. Потом он продолжал двигаться на запад, и 18 июня 1541 года он и его люди стали первыми европейцами, которые увидели реку Миссисипи, которой он дал подходящее название Гранде («Великая»). Место, где было сделано это открытие, не известно точно, но, возможно, оно находилось в нескольких милях к югу от современного города Мемфис, штат Теннесси.