A plot of land at the corner of Bedford Avenue and Hewest Street was purchased, and plans were drawn up for an edifice in the Gothic style. Ground was broken on October 12, 1895, and the cornerstone was laid on December 25 that same year. The completed church was consecrated on December 6, 1896. In December 1915, the Evangelical Lutheran Church of St. Barnabas, located on Lenox Road near Flatbush Avenue, proposed that the two congregations merge. St. Barnabas was without a pastor and offered their church building (which was apparently not completed) as a permanent place of worship. The merger was approved by both congregations in January 1916. As part of the deal, the Church of the Redeemer would "supply whatever can be used to furnish [the] church auditorium..." The old Redeemer property on Bedford Avenue was sold to a synagogue.
After only thirteen years on Lenox Road, the congregation commissioned Mayers, Murray & Phillip of B. G. Goodhue Associates to design a new edifice on Ditmas Avenue between 21st and 22nd Streets. The neo-Gothic building was octagonal in shape and featured a pyramidal copper roof surmounted by a cupola. The completed church was dedicated on February 10, 1929. In 1973, the congregation merged with the Flatbush Presbyterian Church, located nearby at 494 East 23rd Street near Foster Avenue. The combined congregations are known today as the Flatbush Church of the Redeemer.

The organ in the original church building on Bedford Avenue was built in 1896 by Müller & Abel of New York City. It was then moved to the former St. Barnabas Church on Lenox Road in 1916. In 1929 it was rebuilt with some tonal changes and a new console at moved. to the new Redeemer location on Ditmas Ave. at 22nd St.

Information from Müller & Abel opus list, compiled by Stephen Pinel

Originally in old building in Williamsburg section, which stands and in 1970 was used as a synagogue. Electrified by Aeolian-Votey in 1929, using new chests (3-41rk); specification similar to German Zion.