Paradise Missionary Baptist Church developed from a community Sunday school created by Dinah Watts Pace in the Atlanta neighborhood of Summerhill in 1865. In 1870, the church was officially formed and named Pleasant Grove Baptist (located on Grove Street) under the leadership of Rev. Robert Epps, who resigned in 1875. Rev. Epps' successor, Rev. C.O. Jones, helped to grow the church's membership, and the congregation moved to a larger location on Reed Street.

The church was officially named Reed Street Baptist under the leadership of Rev. C.O. Jones. It was finally given the name Paradise during the tenure of its longest-serving pastor, the Rev. Dr. Clifford Nathaniel Ellis, 1934-1980.

*Under his leadership, Reed Street/Paradise grew in unprecedented terms, which led to major renovations of the Fraser Street church, the construction of a state-of-the-art Educational Building, major bus ministries, and the establishment of new church auxiliaries. When construction of the Atlanta Fulton County Stadium forced relocation of the church, Rev. Ellis provided strong guidance, leading the church to a new northwest community location.

Rev. Ellis founded the WSB Chariot Wheels Radio Program, one of the first African-American gospel broadcasts in the nation. He also spearheaded the first integrated audience at the Atlanta Municipal Auditorium during the Convention of the Alliance of World Churches. His affiliations included membership on the Board of the National Baptist Convention, USA, Inc., and the Southern Christian Leadership Conference. He was a member of Omega Psi Phi Fraternity. Rev. Dr. Ellis was married to Vashti Scott Ellis, a sister of the legendary W.A. Scott, II, founder of the Atlanta Daily World, one of the oldest African-American newspapers still in existence in the United States.* The church has had a total of 11 pastors and four interim pastors: Robert Epps (1870-1875), C.O. Jones (1876-1900), J.A. Pinson (1901-1902), Dr. Edwin Posey Johnson (1902-1929), Dr. Ralph W. Riley (1930-1932), Dr. Clifford Nathaniel Ellis (1934-1980), Dr. Nathaniel T. Young (1980-1981), Edward William Lumpkin (1981-1989), W. Thomas Pullen Jr. (June 1989- January 1990), James Edward Bullard (1990-1992), Stanley Calloway (1992-1995), Associate Pastor Lewis E. Baker, Sr. (1995-1999), Dr. Jesse J. Walker (1997-2002), Associate Pastor Charles W. Walker, Sr. (2002-2004), Dr. Charles A. Harper III (2004-Present)

In 2018, Paradise Missionary Baptist Church completed a historic church graft with Cornerstone Community Baptist Church, with Rev. S. Tarnace Watkins, Sr. assuming the leadership position as executive pastor at Paradise.*

Paradise currently stands in Atlanta's Bankhead neighborhood at 1711 Donald L. Hollowell Parkway.

* Taken from the history section of the Paradise Missionary Baptist Church website.