Де Сото отплыл из Сан-Лукар-де-Баррамеда 7 апреля 1538 года, сопровождая целую эскадру, отправлявшуюся в Мексику, из-за опасений короны нападений со стороны французских судов, поскольку Испания все еще находилась в состоянии войны со своей северной соседкой. Плавание прошло без приключений, и после недельной остановки на Канарах 9 июня экспедиция прибыла в Сантьяго-де-Куба. Здесь новый губернатор острова провел укрепление фортификаций города, который перед этим подвергся нападению, сделал ряд ожидавших его административных дел и направился со своей конницей в Гавану, отправив семью и солдат туда же морем.
Гавана встретила нового губернатора 1 ноября и, не теряя времени, он приступил к первым приготовлениям похода во Флориду. Для лучшего представления об ожидавших его там условиях он сначала поручил капитану Хуану де Аняско обследовать побережье полуострова и найти на нем подходящий порт. Параллельно с этим он приобрел четыре больших поместья, которые могли бы снабжать экспедицию всеми необходимыми продуктами, скотом и лошадьми в дополнение к закупкам у местных производителей.
Перед самым отплытием экспедиции во Флориду по пути в Испанию неожиданно прибыл партнер де Сото Понсе де Леон, который распродал в Перу землю и дома Эрнан. На состоявшейся встрече партнеры поссорились в отношении распределения своих капиталов и расходов настолько, что на другой день после подписания по настоянию губернатора нового договора между ними де Леон начал процедуру по его аннулированию. Этой неприятной для обеих сторон тяжбе предстояли длительные перипетии, и партнеры разъехались в серьезной ссоре.
Де Сото отплыл из Гаваны 18 мая, а 30 мая его отряд уже высаживался на берегу Флориды в сегодняшнем заливе Тампа и вскоре начал свое длительное перемещение по огромным землям этой почти не исследованной территории. Самое первое местное поселение, встретившееся им на пути, преподнесло им сюрприз: здесь они обнаружили испанца Хуана де Ортиса, выжившего после 12 лет страшного плена у индейцев после крушения экспедиции Нарваэса. Ортис оказался очень ценным переводчиком в дополнение к тем нескольким индейцам, захваченным во время исследовательского похода Аняско. Теперь де Сото приготовился к проникновению в глубь территории, но сначала он отправил все суда, кроме бригантин, на Кубу за продовольствием, которое должно было быть доставлено позже, и выслал вперед группу разведчиков для предварительного изучения обстановки. Губернатор делал это регулярно, что приносило очень полезные сведения и помогало избегать неприятных неожиданностей. На берегу залива в Тампе было оставлено небольшое подразделение для связи с судами.
Флорида была населена многочисленными племенами с различным уровнем развития и зачастую несхожими языками, что делало работу переводчиков довольно затруднительной, а иногда и просто невозможной. Одним их здешних племен были индейцы майами, которые дали название реке, в устье которой потом возник одноименный город. Довольно скоро испанцы обнаружили, что культура здешних племен была настолько примитивной, что они едва обеспечивали себя жалким пропитанием и не могли служить опорой для их крупной экспедиции, которая уже в первые недели столкнулась с проблемой голода. Положение с продуктами, за рядом исключений, постоянно ухудшалось, а болотистая почва, озера, болота, труднопроходимые заросли, изводящие насекомые и страшная влажная жара изматывали людей и лошадей, делая продвижение медленным и тяжелым Не пришлось долго ждать и столкновений с местными жителями, которые приводили к потерям убитыми и ранеными.
В надежде найти богатые поселения и драгоценные металлы испанцы постоянно расспрашивали встречавшихся жителей о местах, где они могут быть, и двигались в указанных ими направлениях, одним из которых стал район племени аппалачи. Однако, дойдя до него, они не обнаружили никаких признаков богатств, но столкнулись со зловещими следами гибели экспедиции Нарваэса, что лишь усилило и без того нерадостное настроение путешественников. К этому времени они преодолели уже свыше 110 очень трудных лиг от места высадки в заливе Тампа. У аппалачей были найдены большие запасы кукурузы, тыквы, бобов и сушеных слив, которые могли обеспечить пропитание на месяцы наступавшей зимы, а поскольку почва была здесь сухая, де Сото принял решение зазимовать на этом месте. Он одновременно отправил бригантины на Кубу сообщить его жене, оставшейся там вместо него губернатором, о положении дел с экспедицией и привезти столь нужное продовольствие.
Прошло несколько месяцев, но приходившие неоднократно за это время к побережью Флориды бригантины не смогли обнаружить отряд де Сото, который в марте наступившего нового года снялся с лагеря и направился на север к еще одному обещанному индейцами богатому району Кофитачеки. Но и здесь их путь оказался трудным в связи с обилием рек, некоторые их которых приходилось переходить по два дня, теряя при этом время и утонувших людей. Вскоре голод и болезни превратились в постоянных спутников измученных конкистадоров, ряды которых продолжали редеть. К этому времени общая численность отряда значительно возросла за счет набираемых проводников, новых переводчиков и носильщиков, которых стало уже больше, чем испанцев. Кормить их стало совершенно нечем, и де Сото был вынужден почти всех их распустить.
В апреле путешественники добрались до Кофитачеки, где с удивлением столкнулись с остатками пребывания здесь экспедиции Лукаса де Аильона. Но местные индейцы стояли на значительно более высокой ступени развития, чем те, с которыми они встречались до этого. Испанцы восхищались не только изобилием продуктов, но и замечательными одеждами, сделанными из кожи с красивыми украшениями из разноцветных перьев и жемчуга, который мог представлять собой определенную ценность. Место расположения поселений в области сегодняшней Огасты в штате Джоржия на берегу широкой реки Саванна было очень приятным, со здоровым климатом и поблизости от берега Атлантического океана, В дополнение к этому здешние индейцы во главе с женщиной-касике оказали им очень щедрый дружеский прием, что побудило целый ряд участников отряда говорить об основании испанской колонии именно там. Однако подобные разговоры встретили решительный отпор со стороны де Сото, который был твердо настроен найти нечто подобное Перу вместе с богатствами второго Атауальпы, что породило первые тревожные голоса разногласий среди членов экспедиции.
Под давлением губернатора обескураженные конкистадоры, снова руководствуясь сообщениями индейцев, повернули отсюда на северо-запад, где вскоре опять попали в земли нищих индейцев, где отбирали у них силой последние жалкие запасы. Так отряд добрался примерно до широты теперешнего города Чаттануга в штате Теннесси, и это стало самой северной точкой их экспедиции. В этом более благоприятном месте индейцы оказались мирными и имели достаточно продуктов, чтобы дать усталым путешественникам возможность устроить себе некоторый отдых в их скитаниях наугад по неизвестным и бедным землям.
Осенью 1540 года, то есть после года и нескольких месяцев высадки во Флориде, они решили двинуться на юг в сторону залива Мобил. На этом пути они впервые за все время пребывания во Флориде подверглись смелому и ожесточенному нападению индейцев у поселения Мовилла, что привело к кровавой битве, в результате которой свыше 20 испанцев погибли и около 250 получили ранения, а потери местных воинов были значительно большими. После такого тяжелого сражения отряд остановился на отдых на целый месяц. Там до них дошли слухи, что дальше на — было море. Они обрадовались, считая, что там их могут ждать бригантины с продовольствием. Перед лицом надвигавшейся зимы де Сото счел необходимым перебраться на другое место, но он не хотел идти на побережье, поскольку, зная настроение людей, боялся, что оттуда ему уже вряд ли удастся снова затащить их в глубь Флориды. С другой стороны, он опасался, что возможная встреча с бригантинами приведет к передаче неблагоприятных сведений о неудачах экспедиции и создаст дополнительные сложности с ее продолжением.
Теперь губернатор повел отряд снова на северо-запад и, перейдя на территорию сегодняшнего штата Миссисипи, остановил его на зимовку в поселении Чакаса, где было всего 20 домов, которые не могли разместить всех людей, но даже в них при разведенных кострах испанцы страдали от сильного холода Индейцы там были настроены мирно, но к концу зимы они неожиданно напали на пришельцев и подожгли их жилища. В завязавшейся схватке во время пожара погибло одиннадцать человек и 50 столь нужных лошадей, не говоря уже о потере почти всех запасов и снаряжения. У путешественников сгорела даже одежда, и они были вынуждены продолжать путь полураздетыми. В марте 1541 года этотразоренный отряд покинул вероломную Чакасу в поисках богатых земель и драгоценностей.
Дальнейшие скитания отряда сопровождались почти непрекращающимися нападениями индейцев, голодом и другими лишениями. Невероятно ослабленные всеми испытаниями, испанцы стали терять надежды на обретение богатств в этой негостеприимной земле, что подрывало их моральный дух. Однако, верные своему аделантадо, они сохраняли к нему доверие, убеждая себя в том, что он должен найти второе Перу во Флориде. В июне экспедиция вышла на берега удивительно широкой и могучей реки, которую она назвала Рио-Гранде — Большая река. То была грандиозная Миссисипи (от индейского «Меаот Массипи», что означало «Отец Вод»), и люди де Сото стали первыми европейцами, которые увидели это настоящее чудо природы. Целый месяц понадобился испанцам для постройки лодок, чтобы совершить переправу, после чего они продолжили путь на запад через болота и озера бассейна невиданной реки и затем достигли прерий Среднего Запада, где встретились с неизвестными европейцам племенами индейцев сиу и команчи, которым впоследствии еще предстояло немало борьбы за свои земли.
Там, в южной части сегодняшнего штата Арканзас, они остановились в поселении Колигуа, где узнали от местных жителей, что дальше на западе преобладают пустынные земли, что большее число городов находилось на юго-востоке, а за ними было море. Де Сото, понимая общую измотанность отряда и желая теперь уже сам сообщить с побережья известия о делах экспедиции на Кубу, решил идти в сторону моря. Тем временем приближалась их третья зима во Флориде, и теперь у них