The new church, a building in the Early Decorated style with seating for 600, was designed in competition by Raphael Brandon and Henry M. Eyton. S.S. Teulon and Charles Gray were among the unsuccessful competitors. The central entrance was flanked by two tiers of blind arcading; above was a large ‘west’ window, and, at the south-east corner, a bell-turret with a spirelet. Inside, the chief feature of interest was a hammer-beam roof with foliated spandrels. The old schoolroom was incorporated into the site, but hopes, briefly entertained, that land beyond in Hyde Park, little frequented at this point, might be obtained to make a larger overall site were not realized. As it was, the narrow, hemmed-in situation made galleries and a clerestory necessary. To avoid hanging rods inside the church, access for opening and shutting the clerestory windows was provided along outside passageways.
Building work began in February 1860, and the church was completed a few days before its consecration by the Bishop of London on 30 March 1861, the entire cost, £3,600, being met by subscription. The contractors were Dove Brothers.
Both the neighbouring houses were pubs: the Queen’s Head to the east, and the White Hart, rebuilt eastwards of its old site following its demolition for Albert Gate. This situation gave rise to the soubriquet ‘the heaven between two hells’. In fact the pubs seem to have been quite respectable, and one landlord of the White Hart was a highly regarded churchwarden.The building had a fairly short life. Proposals were put forward in 1899 which, despite local protest, led to a new Holy Trinity Church being built on ground provided by the 1851 Commissioners in Prince Consort Road. The old church was pulled down in 1904 and its site, along with much of Park Side, was redeveloped with shops and flats.