Since 1842, Troupville had been served by Methodist preachers of the Georgia Conference. In 1859, the citizens of Troupville moved their town to the newly arrived railway and changed the name to Valdosta. The Methodists held services in the Masonic Lodge and courthouse until 1866. In the 1861 Minutes, Valdosta appears for the first time with Rev. Samuel E. Randolph appointed pastor of the circuit. Associated with the early days are Rev. Wilkins of Naylor, and Major A.J. Bessant, a lawyer and lay preacher, who began the Sunday school. In 1896, the original wooden building was replaced by a brick building which burned in 1904. Immediately the present sanctuary with classrooms and bell tower was begun. The Strickland Memorial Education Building was completed in 1941, later expanded. In 1960, the church was renovated and an additional unit added. After 23 years as part of a circuit, in 1882 Valdosta First became a station. It has hosted the annual session of the South Georgia Conference in 1896, 1906, 1918, 1927, 1941, 1958, 1969, and 1980. This church has given leadership to establishing missions and churches: Center Hill in 1898, Remerton in 1901, Wesley Memorial in 1904, Forrest Street in 1941, Park Avenue in 1954, Westview in 1957, and Kelley in 1962.
In 2002, the church had an active Prayer Ministry and built a Habitat for Humanity home. The church celebrated its 100th anniversary in 2004. In 2008, Generous Living, a program which coordinates donations such as cars and appliances for the needy
In 1998, Kelley UMC merged with Valdosta First. Kelley bore the name of Rev. W. A. Kelley as of 1965 "by a vote of the congregation as a special tribute of love and affection to the man who founded the church in 1962." The church building was a gift to the South Georgia Conference from the Presbyterians who from 1944-1962 had sponsored a church known as Southside Presbyterian Chapel then renamed Cecil Thompson Chapel. Like the Presbyterians, Kelley Methodist was known as Southside from 1962-1964. It was a station church except for 1974-1976 when Westview was part of the charge. From 1976-1984, Dr. John Curtis, Professor of Sociology at Valdosta State College and a minister in this conference, served them part-time.