At the time of the Revolutionary War the valleys, mountains and ridges now included in DeKalb County were in the heart of the great Cherokee Nation. Important inter-tribal councils met at the big Indian village of Willstown, named for the half-breed Chief Redheaded Will and composed of many scattered settlements over much of the area now included in DeKalb county. To the south was Turkeytown, named for Chief Turkey, and Path Creek (now Guntersville) was located to the northwest.

By 1776 the Cherokee Nation had established a policy of favoring the British government over the restless colonists who had encroached upon their lands and had ignored many treaty obligations. Taking advantage of the Indian resentment against the colonists, the British sent agents to encourage Cherokee raids. Soon after the war began, Alexander Campbell was sent to live with the Cherokees at Willstown (now Fort Payne). Campbell worked with Alexander Cameron and other British agents to arouse the Indians to action by promises of clothing and territory. Warriors were supplied with guns and ammunition and were admonished to return with scalps rather than prisoners.

At the end of the Revolutionary War a separate peace treaty was signed between the Americans and the Cherokees, but the bitter hatred felt by both sides was not quieted by treaties and attacks continued. In June of 1794, President Washington met with the Chickamauga Indian, Doublehead, in Philadelphia and signed a treaty. In October of 1794 a total of 40 Cherokee chiefs signed another peace treaty. These chief included Bloody Fellow, Bear at Home, Thick Legs, Broom, Little Turkey, John Watts, the Glass, Pathkiller, Stallion and Tallatuskee.

The days of war councils and scalp dances at Willstown were over. The new century began with the advent of missionaries and church missions in the Cherokee Nation. The movement was started by the Moravians at Springplace, followed by the Presbyterians at Tellico in 1803, at Brainerd in 1817, and at Willstown in 1824. The Methodist missions first appeared in 1825, when nine schools, including on in Wills Valley, were started.

Meantime, white settlers were venturing further into Wills Valley and other lucrative areas of the Cherokee Nation, and by 1830 were agitating for the government to buy this territory. In 1835 a small minority agreed to sell their lands and the Treaty of Echota was signed. Although the spokesman for the nation, Chief John Ross, proved that a majority of the Cherokees opposed the treaty, it was enforced by President Andrew Jackson. The treaty stipulated that the Indians were to be removed by may 26, 1938 and on May 10 of that year General Winfield Scott issued orders for forced removal. The Cherokees were to be rounded up and placed in stockades until all were ready to start west. Captain John Payne was dispatched to Willstown, where a stockade was erected near a large spring and named Fort Payne.

Soon the spot chosen by this army captain developed into a town. As pioneer settlers moved into the valleys and over the mountains, the great Cherokee Nation became another legend.