According to the traditional history of the Cherokees they were the first inhabitants of the Tennessee valley. About 1650 they withdrew from the region to the east of the Cumberland and Sand Mountains, reserving the valley as a hunting ground.

Some years after their withdrawal bands of Shawnees moved southward from Cumberland river and took possession of the Tennessee River country in Alabama. This action angered the Cherokees and they were soon at war with the intruders. Finally after some forty years of warfare, with the aid of the Chickasaws, about 1721, the Shawnees were driven from the country and forced to seek a new home beyond the Ohio. After this long war the Tennessee valley remained without occupants for many years.

About 1765 the Chickasaws moved into the country and formed a settlement in the great bend of the Tennessee River in Marshall County. The founding of this settlement aroused the resentment of the Cherokees, who were soon at war with their former allies. In 1769 a great battle was fought between the two tribes at the Chickasaw village. The Chickasaws were the victors, but their victory was won at such a great loss that they withdrew from the country. This abandoned settlement was thenceforth known as the Chickasaw Old Fields, and a Cherokee settlement was finally made in it. The Chickasaws continued to claim lands on both sides of the Tennessee River. As the first occupants, the Cherokees never ceased to claim a full title to lands on both sides of the river as far west as Big Bear Creek. In view perhaps of their former occupancy of the great bend, the Chickasaws claimed that their boundary line on the north side of the river ran from the Chickasaw Old Fields northwardly to the great ridge dividing the waters of the Tennessee and Cumberland rivers.

In spite of the overlapping of these two tribal claims, both were recognized by the United States. By the Chickasaw treaty of July 23, 1805, that part of the country included between this Chickasaw boundary line on the east and a line on the west, running from the Chickasaw Old Fields northwest to the ridge near the main source of Buffalo River, was ceded to the United States.

By the Cherokee treaty of January 7, 1806, all their territory north of the Tennessee River and west of a line drawn from the upper part of the Chickasaw Old Fields, at the upper end of an island, called Chickasaw Island, northerly so as most directly to intersect the first waters of Elk River, was ceded to the United States.

This triangular tract of country, acquired by these two treaties, became the original Madison County of 1808.

By the treaty of September 20, 1816, the Chickasaws ceded to the United States, with the exception of three reservations, all right or title to lands north of the Tennessee River. This brought about the western enlargement of the county in accordance with the act of the legislature of 1818. By the treaty of February 27, 1819, Alabama acquired all the remaining Cherokee lands within her borders north of the Tennessee river. In this treaty the Cherokees also ceded to the United States, in trust, to be sold for the benefit of the Cherokee school fund, a tract of land twelve miles square. From this treaty with the Cherokees, Madison County ultimately acquired its last territory, giving it its present shape and dimensions.