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