The "Methodist Episcopal Church at red rock," as old church records describe it, was founded sometime before 1886, when the plot on which the church stands was deeded to the trustees of the congregation. That seems an unambiguous beginning, but the truth is that no one is entirely sure today what "at red rock" meant in the late 19^th century. Unlike many rural churches, which are the last institutions to bear the names of vanished towns, there seems never to have been a settlement called "Red Rock" in the area of the church. A church history written in the 1970s tells that the church was named after two founding members, one of whose surnames was "Stone," and one of whose surname meant "Red." Both are buried in the cemetery next to the sanctuary.

Another explanation has it that miners who originally settled the area found "red rocks" in nearby digs; yet another says farmers found them in their fields. Either way, the large piece of red granite in the front yard of the church was not one of those red rocks. It was brought to Red Rock from the Ozarks by Dr. Rose Fisher, a colorful former pastor of the church.

For many years, Red Rock United Methodist Church was yoked with the Hallsville United Methodist Church on a "circuit." Both churches were served by the same pastor and conducted joint programs. Red Rock became independent in 1996.