Established in 1880 in rural Westmoreland County, Virginia, the church grew out of a home mission effort by Episcopal Bishop John Payne.  (The library at Virginia Theological Seminary is named for this same Bishop).  Bishop Payne had returned from missionary work in Africa in the late 1860's or early 1870's and as a home missionary work established a school of black and white students on the grounds of Cavalla his residence near the King George and Westmoreland county line.

Church services were held at the school and also at a reading room in the area.  Some time after Bishop Payne's death, the pastors of King George Methodist Episcopal Church South began leading services and in 1880 a church was built.  Rev. D. G. C. Butts became the first pastor.  D. Gregory Claiborne Butts mentions the church and its founding in his memoir From Saddle to City by Buggy, Boat, and Railway, 1922.

It is not known what the first church building was like.  Despite uncovering rough beams with wooden pins instead of nails, an 'experienced carpenter' did not conclude that there was any clear evidence that the building dated to 1880.