In 1939, when WWII began, rapid military preparations were made at Ft. Benning. With the increased population, Methodist leaders in Columbus felt the need for establishing a new church. First official mention of the new church was at a meeting of Methodist pastors on September 25, 1940, by Rev. G. N. Rainey, District Superintendent. Money was raised and six lots of land were purchased on February 6, 1941. The first Sunday school was held on June 15, 1941, by Rev. Joseph S. Cook, pastor of St. Luke Methodist Church. Rev. Albert L. Hall was appointed in November 1941, and a church building was constructed in October 1942. This sanctuary was dedicated by Bishop Arthur J. Moore on October 4, 1942. The first quarterly conference was held on November 1, 1942, and 16 charter members were reported. Rev. Frank L. Robertson was appointed in 1942, and under his pastorate, the first annex of two small rooms near the pulpit was built. Another building was added in February 1946 for the Boy Scouts and Sunday school classes. In 1947, under Rev. Edwin J. Grimes's leadership, a surplus barracks building was purchased and placed on the church grounds. This was remodeled to provide an assembly room and three classrooms. The present parsonage was built in 1949 on land adjacent to the church buildings. More surplus barracks buildings were purchased in 1949, which allowed for two more classrooms. Chimes were added in 1950.
On July 19, 1953, the name was changed to South Columbus Methodist Church to reflect the fact that members came from all over the city. Groundbreaking for a new sanctuary occurred in 1955, with Bishop Arthur J. Moore laying the cornerstone. The first service was held on May 29, 1955, with all seats filled, including the balcony. A seven-room annex was completed in September 1957, adding much-needed classrooms. The mortgage for the children's building was paid off and burned in February 1964. A lightning strike in 1964 caused a fire in the west end of the sanctuary which led to redecorating it.
During the Vietnam War, there was a decreased membership at South Columbus UMC due to soldiers being deployed. At this time, the pastor wrote notes on bulletins and mailed them to the soldiers where they were stationed. The mortgage for the sanctuary was burned in 1966. The new educational building was completed in September 1967, with Bishop John Owen Smith in attendance. That same year, Wednesday family dinner began. On May 5, 1968, the youth of the church presented the evening service including the leading song, prayers, offering collections and speakers. In 1969, South Columbus UMC planned as many ecumenical programs as possible including Christmas around the world, studies of China and missionaries and laymen from the Temple Israel Synagogue. In May 1978, a tornado went over the church causing terrible damage and, in November 2012, a fire damaged the church's sanctuary. The church's food pantry began in 1974, with the annual rummage sale starting a year later.