St Paul's Church, originally on Wellington Street and later Bishopton Road West, Stockton. The parish was formed in 1875 out of parts of the St. Thomas and Holy Trinity parishes.

It is believed a temporary wooden church existed before the brick church in Wellington Street was constructed. The church of St Paul, in Wellington Street, was designed by J P Pritchett of Darlington and was completed in 1885 at a cost of £3,700. It was a brick building of buff or cream Normanby bricks with stone facings in the 13th century style. The roof was covered with Port Dinorwic slate. The building consisted of a chancel, nave, vestry, organ chamber, south-west porch and bell gable and had a capacity of 417.

The vicarage was built on Bishopton Lane in the Queen Anne style in 1877 at a cost of £1,500. It was demolished in 2005 after standing empty and derelict for a number of years.

In the 1920s parish boundary changes occurred and, as a result, a new building was constructed a little further out of town on Bishopton Road to serve Newtown, Grangefield, Newham Grange and part of Elm Tree. This was built in 1925-26 to a design by W J Moscrop, but never fully completed.

In the 1960s part of the church was dismantled and redesigned by Ian Shuttleworth. This was completed in 1965.  Since 2004 the building has been shared with Newtown Methodists, a fine example of interdenominational cooperation.

The story of the old church did not end in 1925, as in 1930 the church was carefully dismantled and transported by lorry to Blackhall on the Durham coast, a distance of some 16 miles. However because of the pollution in Stockton over the life of the church, it was found necessary to rebuild with the dirty outside brick and stone on the inside. Hence the local name for St Andrew’s church, ‘the inside out church’.   A saving of some £4-5,000 was made over the cost of a new church. So after a 40-year history in Stockton, St Paul’s lives on as St Andrew’s Blackhall.