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