In the 19th century, the site of Fort Payne was the location of Willstown, an important village of the Cherokees who relocated to Tahlequah, Oklahoma during the Cherokee Trail of Tears. For a time it was the home of Sequoyah, who invented the Cherokee syllabary, enabling reading and writing in the language. The settlement was commonly called Willstown, after its headman, a red-headed mixed-race man named Will. According to Major John Norton, a more accurate transliteration would have been Titsohili. The son of a Cherokee adoptee of the Mohawk, Norton grew up among Native Americans and traveled extensively throughout the region in the early 19th century. He stayed at Willstown several times.
During the 1830s prior to Indian removal, the US Army under command of Major John Payne built a fort here that was used to intern Cherokees until relocation to Oklahoma. Their forced exile became known as the Trail of Tears.
By the 1860s, Fort Payne and the surrounding area were still sparsely settled. It had no strategic targets and was the scene of only minor skirmishes between Union and Confederate forces during the Civil War. About the time of the Second Battle of Chattanooga, a large Union force briefly entered the county, but it did not engage substantial Confederate forces.
In 1878 Fort Payne became the county seat, and in 1889 it was incorporated as a town. The community of Lebanon had served as the county seat since 1850. With the completion of rail lines between Birmingham and Chattanooga, Fort Payne began to grow, as it was on the rail line. County sentiment supported having the seat in a community served by the railroad.
In the late 1880s, Fort Payne experienced explosive growth as investors and workers from New England and the North flooded into the region to exploit coal and iron deposits discovered a few years earlier. This period is called the "Boom Days", or simply as the "Boom". Many of the notable and historic buildings in Fort Payne date from this period of economic growth, including the state's oldest standing theater, the Fort Payne Opera House; the former factory of the Hardware Manufacturing Company (today known as the W. B. Davis Mill Building, and home to an antiques mall and deli), and the Fort Payne Depot Museum, formerly the passenger station for the present-day Norfolk Southern Railway. Today it serves as a museum of local history.
The iron and coal deposits turned out to be much smaller than expected. Many of the Boom promoters left the region, and Fort Payne experienced a period of economic decline. That downturn shifted in 1907, when the W.B. Davis Hosiery Mill began operations. This was the beginning of decades of hosiery manufacture in Fort Payne. By the beginning of the 21st century, the hosiery industry in Fort Payne employed over 7,000 people in more than 100 mills. It produced more than half of the socks made in the United States.
Beginning in the 1990s, the North American Free Trade Agreement and the Central American Free Trade Agreement lowered tariffs on textile products imported into the United States, resulting in large increases in sock imports. Many businesses in Fort Payne accused foreign manufacturers, particularly those from China, of engaging in dumping of socks below cost, to force American companies out of the sock business. By 2005, hosiery mill employment in Fort Payne had declined to around 5,500, and several mills had closed. In later 2005 the federal government gained an agreement with the Chinese government to slow the schedule for the removal of tariffs, delaying their full removal until 2008.
Reacting more quickly to changes than at the end of the Boom, in the 1990s business and civic leaders in Fort Payne began to take steps to diversify the city's economy. Several new commercial and industrial projects were developed. The largest was the 2006 construction of a distribution center for The Children's Place stores, a facility that employed 600 people in its first phase of operation.