Before settlement, Clay County was home to the Cherokee Indians, who were a tribe of Native Americans that made their home in Southeastern United States (principally Georgia, the Carolinas and Eastern Tennessee) They were one of the "Five Civilized Tribes" because of their assimilation of European-American cultural and technological practices. During the late 1700s, the first European-American settler, John Covington Moore, settled here in what was then part of Macon County. The first emigrants moved to this area in the early 1830s.
In 1837, General Winfield Scott was hired to gather all the Native Americans in the region and detain them in improvised stockades before transporting them into Oklahoma Territory. Captain Hembree was sent to an area about a mile southwest of Hayesville to construct a stockade to hold the Native Americans until they had all been gathered up. This marks the beginning of the Trail of Tears. The stockade was named after Captain Hembree as Fort Hembree and served as a center of business.
In the Fall of 1860, George Hayes, who was running for Representative from Cherokee County, promised his southeastern constituents to introduce legislation to form a new county. In February 1861 the legislation was introduced and passed by the North Carolina General Assembly.
Clay County was formed primarily from Cherokee County, North Carolina, however a small area was taken from Macon County, North Carolina. In honor of Mr. Hayes, the then new county's seat was appointed Hayesville and the newly formed county was named in honor Henry Clay, famous American statesman, member of the United States Senate from Kentucky.
Despite having been created in 1861, Clay County lacked an organized, formal government until 1868. Later that year, the first post office opened in Hayesville and the first county courthouse was built in 1888, currently it is listed on the National Register of Historic Places.
Throughout the rest of the nineteenth and early twentieth centuries, Clay County has remained largely agricultural.