In 1828, Rev. Morgan Turrentine was appointed to serve the Lee Mission in the territory between the Chattahoochee and Flint Rivers recently ceded by the Creek Indians. In 1830, the Randolph Mission was formed and in 1833, Rev. J.T. Talley was appointed its first pastor. The name was changed to Cuthbert Charge in 1837 or 1838. Under the leadership of Rev. Tillman Purifoy, the congregation built its first building of logs in 1844, known as Shady Grove Campground. That site, located on West Hamilton Avenue, is now the Greenwood Cemetery. The present church was built in 1851, of wood and in the style of the day. It was remodeled in 1907, and brick veneer in 1917. A social hall was added in 1947, and a Sunday school annex in 1956. The sanctuary was completely renovated in 1971. The South Georgia Annual Conference has been held in Cuthbert in 1869, 1886, and 1900.
In 2000, the sanctuary and Fellowship Hall were completely remodeled. During 2000-2001 the church supported Andrew College by furnishing a chaplain, had an active youth program, and supported a missionary family in Lithuania.