Building work for a new church in Addlestone began in 1836, and the church was consecrated two years later. Prior to the opening of this 600 seater church, residents of Addlestone had to walk to Chertsey every Sunday.
Nearly 20 years after it was first opened, further building work took place at St. Paul’s Church with the construction of the Chancel. It was also at this time that a “rare Tucker two-train” tower clock with “dead beat escapement and wooden rod pendulum” was installed.
Further changes took place in 1870 with the installation of gas lighting in the aisles (electricity was not installed until 1914), and in 1883 the box pews were replaced with the current seating, hot water central heating was installed and the building was generally refurbished.
The church has a restored Rest Cartwright organ with pipes from a Hunter pipe organ. This mechanical action organ, first built in 1919, weighs one ton and has 552 pipes that use 1,000 cubic feet of air per minute.
On 12th December 2003, a massive fire sadly destroyed the whole interior of the tower and the roof of the nave. Work is being undertaken to repair and restore the damage.