It began in 1881 as a mission from Marlborough College[1] and was initially housed in the board school at Coleraine Park (now Coleraine Park Primary School).

Three years later it became a mission district, with the college contributing more than a third of the cost of the site for a permanent church.

In 1887 it was consecrated,[1] and the following year it turned into a consolidated chapelry, formed from All Hallows, Holy Trinity and St Paul.

The red brick permanent church was designed by J. E. K. Cutts.

Lack of maintenance in the 20th century led to the organ falling out of use, but in 2009–10 it was removed from the church for restoration, including a Barker lever mechanism.