Although previously known to the Virginia colonists by their other names, a form of "Tutelo" first appeared in Virginia records in 1671, when the Batts and Fallam expedition noted their visit to "Totero Town" near what is now Salem, Virginia. A few years later, the Tutelo / Nahyssan joined the Saponi to live on islands located where the Dan and Staunton rivers join to become the Roanoke River. It was just above the territory of the Occaneechi. For a time, the Tutelo had a settlement in what is now Floyd County, VA on the banks of the New River. Many of the sherds collected there and the small triangular points, suggest a mid- to late 16th-century or an early 17th-century date.