Fayetteville is on State Highway 159 and Farm roads 955 and 1291, twelve miles east of La Grange in eastern Fayette County. It developed from a settlement formed by three families of Stephen F. Austin's Old Three Hundred—those of John Crier, James Cummins, and James J. Ross. The surrounding area was known as Ross Prairie, after Ross. The developing settlement was on the Old San Felipe to Bastrop road and was a stagecoach stop. In 1834 the Breeding family established nearby the first school in what would become Fayette County; some of James J. Ross's children attended classes there. The settlement was called Wadis Post Office in 1835. Jesse Burnam's ferry across the Colorado River was nearby, and during the Texas Revolution Sam Houston and his army used this ferry and then burned it on their march to San Jacinto. From the area came nine men who fought in the Texas Revolution, among them Jerome B. Alexander; the community was for a time called Alexander's Voting Place after him. It was also known as Lick Skillet (Lickskillet), supposedly for the fact that latecomers to the numerous community festivals who complained that all the food was gone were told to lick the skillet. By the 1830s some German immigrant settlers were arriving in the area. The Congress of the Republic of Texas established Fayette County in 1837, and the community of Fayetteville was officially founded shortly thereafter. It was named Fayetteville in 1844, for the birthplace of Philip J. Shaver of Fayetteville, North Carolina. Shaver surveyed the community, named the streets, and donated lots for the Fayetteville Academy and the multidenominational Union Church. Fayetteville had a post office and postmaster during the Republic of Texas, and as of the early 1990s the town had had continuous postal service since 1850.
In 1853 the first group of Czechs entered Fayette County, and that year Tom Batla settled in Fayetteville, becoming its first permanent Czech resident. This group of immigrants was made up of Protestants, and the first Czech Protestant service in the state of Texas was held near Fayetteville in 1856. In 1856 a second group, this time Czech-Moravians, arrived in Fayette County; these were primarily Catholics who, like the Czech Protestants, had left their homeland because of the Austro-Hungarian Empire's occupation of their land. Fayetteville is known as the "cradle of Czech immigration to Texas" because after the Civil War most Czech immigrants to Texas went to Fayetteville first. By the 1870s nearly all of the Anglo settlers and their families had left Fayetteville, which at that time had a large Czech-Moravian population but no Czech-speaking priest. On December 25, 1872, the first Czech Catholic service there spoken in Czech was held by the first Moravian Catholic priest in Texas, Father Josef Chromcik. By the 1880s the population of Fayetteville was predominantly Czech and German. Its citizens were instrumental in the formation of two of the first Czech insurance and fraternal organizations in the state and in the nation—the the KJT (Katolická jednota texaská) and the SPJST (Slovanská podporující jednota statu Texas, known in English as the Slavic Benevolent Order of the State of Texas). Fayetteville was also the site of the organization of the first Czech band in Texas, organized in 1892 and known as the Baca Family Band.
Fayetteville was incorporated on March 2, 1882. In October 1887 the Taylor, Bastrop and Houston Railway built a line through the town. A fire consumed one side of the town square in 1893, prompting the installation of a city waterworks and the establishment of a fire department. The Schumacher Bank opened in 1900; it eventually merged with another bank to form the Fayetteville Bank. The population of Fayetteville was 356 in the early 1980s, when most local residents were involved in raising beef cattle, corn, grain sorghums, or wheat. In 1986 the community had the post office, five churches, and more than thirty businesses, including a bank and a savings and loan. Fayetteville reported a population of 283 in 1990 and 261 in 2000. The Lickskillet Festival is held there each October. During the early 1990s the town had a number of restaurants, hotels, antique stores, and other specialty stores.