The Grade I listed church was designed by Roger Eykyns of Wolverhampton. Building started in 1777, and the church was consecrated in 1779. It was built on land given by Charles Colmore from his Newhall estate. It was the church of Birmingham's early manufacturers and merchants - Matthew Boulton and James Watt had their own pews, which were bought and sold as commodities at that time. It is a rectangular church. The upper part of the tower and spire was added between 1822 and 1823, designed by Francis Goodwin and built by Standbridge and Company. In 1841 the church became a parish in its own right, with land taken from that of St Martin in the Bull Ring. In 1947, St Mark’s Church, King Edward's Road was demolished, and the parish was joined with that of St Paul’s. Bomb damage from the Second World War was repaired between 1949 and 1951 when much of the roof was replaced. The church undertook another restoration between 1985 and 1994. A peal of 10 bells was installed in 2005.
The first documented organ in St Paul's was built in 1830 by James Bishop. It was sited on the gallery at the west end of the church. Banfield enlarged the organ in 1838 including a new Swell division which was probably a replacement for Bishop's Swell rather than an addition. Bevington and Sons rebuilt and enlarged the organ in 1871 and again worked on it in 1897. The organ was moved to its present location in 1927 by Conacher Sheffield & Co. and was extensively rebuilt. However, the organ case could not be accommodated in its new position unaltered. The wings had to be removed and are now joined together to serve as the screen facing the north gallery, along with some recycled pew doors. The side towers could not fit between the mouldings on the north arcade bases, so the entire case-front was raised so that the corbels of the side towers cleared the mouldings. This caused the side-tower cornices to conflict with the arcade capitals, so the cornices were removed. Following war damage and the resulting weather-related damage, the organ was noted to be in a poor state by 1953, notably the Choir division was completely 'bombed out'. Hill, Norman & Beard remodelled the organ as a two manual and pedal instrument in 1964. This is the organ present today albeit with some additions to the piston system added in 1996. There are a mixture of mechanical and electro-pneumatic actions and soundboards of differing compasses. The pipework consists of some of the original Bishop ranks, some second hand pipework from Hill Norman & Beard's stock in 1964 and one partly new stop – the Great Stopped Diapason.
The first ring of bells was added in 2005. Prior to this the church had three bells used as a service bell and clock chimes. A new ring of ten bells was installed to celebrate the 250th anniversary of the St.Martin’s Guild of Church Bell Ringers and officially opened on 25 November 2005. The tenor weighs.
