In 1884 this site, formerly the Seymour Gardens, was purchased for £1100 and later that year John Horbury Hunt was appointed architect for the new church. The foundation stone was laid by the Bishop of Sydney on 30th May 1885 and masonry work was completed by June 1886. A year elapsed before the roof was added and the architect’s decision to use tile ridge-capping, contrary to the direction of the building committee to use lead, finally led to his dismissal.

With a temporary wooden west end, a budget over-run of some £2000 and a threat of litigation by Hunt, All Saints was opened and dedicated on 22nd April 1888. A bay to the nave, a narthex and tower were added from 1938.

The collection of stained glass in All Saints is acknowledged as one of the finest in the Sydney Anglican Diocese; the Manning and Simpson memorials in the south nave were designed by Sir Edward Burne-Jones and manufactured by William Morris & Co and are the only stained glass windows in Sydney from this source.  Those in the narthex are by Norman Carter and commemorate the Rev Rolfe and his son; the east window, the Te Deum, was designed by Andrew Wells of Lyon Wells and Cottier and was removed during World War II and buried in the cellars of St Ives (see 15 Crescent Street) which was the family home of the Simpsons.

The fine organ, built by Bevington and Sons of London, was installed in the church in 1888 shortly after the church was opened and is reputedly the largest and most intact Bevington of its size in existence.