The earliest history of Salem exists as archaeological evidence of Native American tribes from as far back as 8000 B.C. until the middle of the 18th century. Europeans first explored the area of Salem in 1671, when the Siouan-speaking Totero people had a village nearby. Explorers Thomas Batts and Robert Fallam gave the area its first recorded name: Totero Town, after this tribe, who supplied them with a guide to help with further exploration. Fort Lewis, named for General Andrew Lewis, of what is now Roanoke County, was built west of the town in 1752. Salem's Andrew Lewis Middle School (formerly Andrew Lewis High School) was named after General Lewis. Salem became a small settlement serving travelers on the Great Road (roughly the same path followed by US-11 and later Interstate 81 today) and was officially founded in 1802, receiving its charter in 1806. It is not known why the town was named Salem; the most widely accepted explanation is that it was named to honor William Bryan, a prominent citizen, who had moved from Salem, New Jersey.