The First Baptist Church was incorporated on October 15, 1823, making it the second Baptist church on Long Island and the first to be incorporated in Brooklyn. The eleven original members appointed Rev. William C. Hawley, who led services in homes and schoolhouses until funds were secured to build a church on Pearl Street, between Concord and Nassau Streets. The congregation's first baptism was held in the East River at the foot of Fulton Street.

Nicknamed Old First, the church opened one of the country's first Sunday schools in 1824. 95 pupils enrolled in the first class, held at a public school at the corner of Adams and Concord Streets. In 1835, the building on Pearl Street was sold to an Episcopal group and the congregation moved to a new, larger building on Nassau Street, installing a Holbrook and Ware organ in 1837.

In 1840, 33 members of First Baptist Church were dismissed to expand the ministry in Brooklyn Heights. This congregation purchased land from the Pierrepont family and built a new church on the corner of Pierrepont and Clinton Streets. First called East Church, the name was soon changed to Pierepont Street Baptist Church. The spelling was later updated to Pierrepont Street Baptist Church. The two churches operated independently until 1873, when they merged to become First Baptist Church in Pierrepont Street. First Baptist Church was destroyed by fire earlier that year, requiring the new congregation meet at the church on Pierrepont and Clinton Streets.

The new congregation's 900 members, led by Rev. Jesse B. Thomas, strained the small church building. In 1892 the building was sold to the Brooklyn Savings Bank and construction began on a new building at 360 Schermerhorn Street. During construction, services were temporarily held at the Polytechnic Institute and the Academy of Music. The new church was dedicated in 1895 with seating for 2,000 and an Odell organ. Although the church continued to legally operate as First Baptist Church in Pierrepont Street, the building was called Baptist Temple. The Bible School operated in the church basement, enrolling 1,328 pupils in 1896.

Baptist Temple was destroyed by fire in 1917. While it was being rebuilt, services were held at the Academy of Music, Central Y.M.C.A., and Hanson Place Church. The new building opened in 1918 with a 4-manual J.W. Steere and Son organ. During the church's 100th anniversary celebration, the mortgage taken out to rebuild Baptist Temple was publicly burned.

In the years following World War II membership declined. By 1955, the church was having financial problems, allowing the organ to fall into disrepair, and by the 1980s neglect left it almost unplayable. A 1991 campaign successfully raised enough money for a full restoration, and in 1995 the church was placed on the National Register of Historic Places and the State Register of Historic Places. Despite these milestones, attendance continued to decline, and by 2003 Baptist Temple had only 40 members.

In 2011, the church changed its name to Recovery House of Worship, and on Easter 2022 to Next Step Community Church. The 2020s saw an increase in attendance, and by 2023, membership was at 200. The church introduced several popular programs to meet community needs, including a soup kitchen, food pantry, children's church, and mother and baby ministry.