It is uncertain when Randall Methodist Church began, but it is agreed that the church was named for John Randall who died in 1805. According to Francis Asbury's journal he visited the John Randall home on six occasions, the first time on 15 Feb 1785 to borrow a horse since his was injured. On May 16-17, 1807, Rocky River Circuit Quarterly Conference was held at "John Randall's Church" and Henry Ledbetter, George Allen, Isham Randle were delegates. In 1813 three and a half acres were given by John Snuggs where the present church now stands. Original trustees were: John Christian, George Allen, John Randall, Wyatt Randall, and Henry Ledbetter (1769-1852, born in Virginia, entered ministry from this church and served in the area for eight years). In the old cemetery at the rear of the church is this tombstone: "In memory of John Randle, Esq., who died on the 13th of February, 1824, in his 40th year."

In 1813 Randall's Church reported 34 white members and their 36 Negro slaves. Early churches incorporated galleries for slaves who attended and were given Christian training.