Испанцы медленно продвигались по заболоченной лесной местности, изрезанной реками; часто приходилось наводить временные мосты. Индейцы были враждебно настроены, так как в их стране уже побывали солдаты Нарваэса и память о жестокости испанцев была еще свежа. По испанским источникам, солдаты Нарваэса отрезали нос одному из флоридских вождей, а его мать затравили собаками.

Услышав о приближении отряда Сото, индейцы уходили из своих деревень и укреплялись на холмах, окружая их частоколом.

В октябре отряд повернул на запад, к морю, и остановился на зимовку близ залива Аппалачи, где было достаточно продовольствия. Сото вызвал туда свои суда и послал их далее на запад - разведать побережье на 100 лиг.

В марте следующего, 1540 года Сото двинулся от залива Аппалачи на северо-восток, на поиски области, где верховным вождем является женщина, собирающая дань тканями и золотом от подвластных ей племен: такие сведения собрал Ортис у местных индейцев. Сото действительно нашел женщину-вождя на текущей в Атлантический океан реке Саванне, в долине ее среднего течения. Однако резиденцией этой правительницы был бедный поселок; ценных тканей и золота. У нее не было, и поделиться с непрошенными гостями она могла только жемчугом, который ее "подданные" добывали в реке и ее притоках.

От этой малопривлекательной "столицы" Сото поднялся в поисках Семи городов в северном направлении вверх по долине Саванны до параллели 35° с.ш. и проник в горный район - юго-западный участок Голубого хребта Аппалачской горной системы. Возможно, что конкистадора привлекали рассказы о большой реке, начинающейся в этом районе и текущей на запад (Теннесси, системы Миссисипи). Но он не перевалил Аппалачи, а снова, увлеченный рассказами о больших городах на юго-западе, повернул к ним. Сото прошел вдоль южного участка аппалачского "Подножия" (Пидмонт), то высылая вперед с переводчиками наиболее ловких солдат, которые "лаской и приветом" убеждали индейцев мирно пропустить отряд, то силой прокладывая себе путь.

Теперь испанцы пересекали верховья рек, текущих через плато Пидмонт и приморские низменности в южных направлениях и несущих свои воды в Атлантический океан (система Олтамахо) и в Мексиканский залив (системы Аппалачи-колы и Алабамы).

Вождь одного из местных племен вызвался сопровождать испанский отряд и привел непрошенных гостей в поселок на берегу большой реки (вероятно, Алабамы). Поселок был окружен высоким земляным валом и бревенчатым забором с двумя воротами. Через каждые пятьдесят шагов у забора сооружены были сторожевые башни, и в каждой помещалось до восьми воинов. Поселок насчитывал восемьдесят больших деревянных домов; некоторые из них были так велики, что в них якобы размещалось по тысяче человек. Испанцы, увидев дома-крепости, решили, что их предательски заманили в ловушку, поспешно отошли назад и атаковали поселок. Они выбили топорами деревянные ворота, ворвались внутрь и подожгли дома. Со стороны индейцев сражались не только мужчины, но и женщины. Сото был ранен, но остался в строю, чтобы его люди не пали духом.

Индейцы мужественно сопротивлялись, однако когда огонь распространился на весь поселок, обратились в бегство. Бой продолжался девять часов. Испанцы потеряли более восьмидесяти человек; часть их погибла в бою, остальные вскоре умерли от ран. Сведения о потерях индейцев, как всегда, разноречивы: историки говорят о двух, пяти, семи и даже десяти тысячах индейцев, частью убитых во время резни на "городских" улицах, частью сгоревших в домах. Тем не менее, людские потери, понесенные испанцами, и гибель нескольких десятков лошадей повергли их в уныние. Золота они не нашли, окружены были враждебными племенами; многие поэтому настаивали на возвращении на Кубу (испанские суда находились сравнительно недалеко от места битвы). Но Сото не хотел отступать. Он предоставил своим солдатам двухнедельный отдых и двинулся в середине ноября дальше на запад, сломив сопротивление индейцев, пытавшихся задержать его отряд у переправы через реку.