In volume I of his book The Tennessee (part of The Rivers of America series), Donald Davidson mentions a Cherokee legend of a great battle fought at Muscle Shoals between the very first Cherokees and a group of white men. This would, I believe, been prior to DeSoto's peregrinations through here. Also, I a bit foggy on it, after all these years, but I recall that there was a story that the Welsh Prince Madoc sailed into Mobile Bay in the twelfth or thirteenth century, and moved northward, leaving European-style earthworks in several locations in Alabama. I can't vouch for the Madoc legend, but I have heard the Muscle Shoals story from several sources.
Bill in Alabama