When the town of Stillmore was organized, a group of Methodists began to congregate and hold services. A membership was started in the spring and summer of 1892, under Rev. J. Snyder's leadership. Henry J. Biddenback was the first to join on March 13, 1892, and Mrs. Annie Prescott Harper was an early member joining on December 13, 1892. The first pastor listed in the Register of Pastors was Rev. C. E. Choate, who was appointed in December 1892. George M. Brinson, the founder of Stillmore, donated land for the church building on September 23, 1892. The trustees of the church at that time were Henry J. Biddenback, William J. Saxon, and Wafford Johnston. The first Sunday school superintendent was Albert Wafford Johnston. George M. Brinson donated the building materials and a wooden church structure similar to the central section of the Baptist Church was built. This first church had a high steeple and was raised on high brick pillows. It was used until the early 1900s when lightning struck the steeple and the church was destroyed by fire
. The Methodist congregation was able to worship in the Baptist Church until a second building was completed in 1907. This sanctuary included a brick parsonage behind the church. Rev. R. S. Stewart was pastor at this time. The parsonage was destroyed by fire in 1913.
The present church is a reproduction of the original brick structure having been rebuilt within the brick walls. There were some alterations in the architectural design in that the ceiling in the chancel section was raised to that of the auditorium section. The present sanctuary was completed in 1914. Also in that same year, George M. Brinson deeded more land to the church and the parsonage was rebuilt a safer distance away from the church in case of another fire. In 1999, Stillmore UMC was listed on the National Register of Historic Places. The Romanesque Revival building was designed by Charles Edward Choate, a Methodist minister.