Через день-два после высадки к испанцам явился их земляк Хуан Ортис, один из немногих уцелевших людей из экспедиции Памфило Нарваэса, одиннадцать лет живший на побережье Флориды среди индейцев. По словам Ортиса, его спасла от смерти жена местного вождя. Лишенный возможности свободно передвигаться, Ортис мало знал о внутренних районах Флориды, но был очень полезен Сото как переводчик.
Оставив для охраны судов часть солдат, Сото двинулся с остальными в глубь страны, на север. По дороге испанцы встречали крупные селения (в иных было больше 600 домов). Участники экспедиции прежде всего начали расспрашивать, где
Испанцы медленно продвигались по заболоченной лесной местности, изрезанной реками; часто приходилось наводить временные мосты. Индейцы были враждебно настроены, так как в их стране уже побывали солдаты Нарваэса и память о жестокости испанцев была еще свежа. По испанским источникам, солдаты Нарваэса отрезали нос одному из флоридских вождей, а его мать затравили собаками.
Услышав о приближении отряда Сото, индейцы уходили из своих деревень и укреплялись на холмах, окружая их частоколом.
В октябре отряд повернул на запад, к морю, и остановился на зимовку близ залива Аппалачи, где было достаточно продовольствия. Сото вызвал туда свои суда и послал их далее на запад - разведать побережье на 100 лиг.
В марте следующего, 1540 года Сото двинулся от залива Аппалачи на северо-восток, на поиски области, где верховным вождем является женщина, собирающая дань тканями и золотом от подвластных ей племен: такие сведения собрал Ортис у местных индейцев. Сото действительно нашел женщину-вождя на текущей в Атлантический океан реке Саванне, в долине ее среднего течения. Однако резиденцией этой правительницы был бедный поселок; ценных тканей и золота. У нее не было, и поделиться с непрошенными гостями она могла только жемчугом, который ее "подданные" добывали в реке и ее притоках.
От этой малопривлекательной "столицы" Сото поднялся в поисках Семи городов в северном направлении вверх по долине Саванны до параллели 35° с.ш. и проник в горный район - юго-западный участок Голубого хребта Аппалачской горной системы. Возможно, что конкистадора привлекали рассказы о большой реке, начинающейся в этом районе и текущей на запад (Теннесси, системы Миссисипи). Но он не перевалил Аппалачи, а снова, увлеченный рассказами о больших городах на юго-западе, повернул к ним. Сото прошел вдоль южного участка аппалачского "Подножия" (Пидмонт), то высылая вперед с переводчиками наиболее ловких солдат, которые
Теперь испанцы пересекали верховья рек, текущих через плато Пидмонт и приморские низменности в южных направлениях и несущих свои воды в Атлантический океан (система Олтамахо) и в Мексиканский залив (системы Аппалачи-колы и Алабамы).
Вождь одного из местных племен вызвался сопровождать испанский отряд и привел непрошенных гостей в поселок на берегу большой реки (вероятно, Алабамы). Поселок был окружен высоким земляным валом и бревенчатым забором с двумя воротами. Через каждые пятьдесят шагов у забора сооружены были сторожевые башни, и в каждой помещалось до восьми воинов. Поселок насчитывал восемьдесят больших деревянных домов; некоторые из них были так велики, что в них якобы размещалось по тысяче человек. Испанцы, увидев дома-крепости, решили, что их предательски заманили в ловушку, поспешно отошли назад и атаковали поселок. Они выбили топорами деревянные ворота, ворвались внутрь и подожгли дома. Со стороны индейцев сражались не только мужчины, но и женщины. Сото был ранен, но остался в строю, чтобы его люди не пали духом.
Индейцы мужественно сопротивлялись, однако когда огонь распространился на весь поселок, обратились в бегство. Бой продолжался девять часов. Испанцы потеряли более восьмидесяти человек; часть их погибла в бою, остальные вскоре умерли от ран. Сведения о потерях индейцев, как всегда, разноречивы: историки говорят о двух, пяти, семи и даже десяти тысячах индейцев, частью убитых во время резни на "городских" улицах, частью сгоревших в домах. Тем не менее, людские потери, понесенные испанцами, и гибель нескольких десятков лошадей повергли их в уныние. Золота они не нашли, окружены были враждебными племенами; многие поэтому настаивали на возвращении на Кубу (испанские суда находились сравнительно недалеко от места битвы). Но Сото не хотел отступать. Он предоставил своим солдатам двухнедельный отдых и двинулся в середине ноября дальше на запад, сломив сопротивление индейцев, пытавшихся задержать его отряд у переправы через реку.