Anglican. The parish church is located in OS Grid Square SW4730 and was dedicated to St Mary the Virgin. The present church was built in 1833-5, and opened on 15th November 1835. It was consecrated by the Bishop of Exeter in 1836. The architect, Charles Hutchens, was a native of St Buryan, a few miles west of Penzance. The Church replaced a chapel building which had been on the same site, and when it was completed it was still actually known as the Madron Chapelry of Penzance as it came under the parish of Madron.
St Mary's became a Parish Church with a Vicar of its own on 24 March 1871, the Bishop of Exeter being the patron, although the bishop still had to consult the Vicar of Madron before he appointed a priest to the living. In March 1985, the interior of the church was devastated by fire which completely destroyed the High Altar and Reredos and the organ in the west gallery.
The church consists of a chancel, nave, north and south aisles, vestry, organ loft and side galleries. At the restoration of 1987, the opportunity was taken to divide the church by glass screens to provide a narthax or vestibule, with kitchens, etc. and to create a new Chapel of the Resurrection. Meeting rooms were also provided upstairs at gallery level. The upper casing of the organ and pipes (part dating from 1675) came from the University Church at Oxford; the new action and console were constructed by Lance Foy of Truro. The Mayor's seat, by the South wall near the font, was restored by the Town Council; it was believed to have been in the previous building pre-1835 and had not been used by the Mayor for some 150 years. It was used in the sanctuary, prior to the fire of 1985, as a sedilia for the priest and his assistants.
A relic from an even older chapel of St Gabriel and St Raphael, sited near the harbour and dating from 1425, is the remains of a granite cross which can still be seen outside the south-east corner of the church. Relics of St Mary's chapel, which still survive, are the alms box (dated 1612) and the Holy Water Stoup found towards the back of the church. The bowl of this was the original font. The weather vane on top of the church dates from 1789.
The churchyard has been restored by Penwith District Council in whose care it remains. There has been much replanting of shrubs; seats have been provided and all paths renewed. It faces out to Mount's Bay.
Following the parish's union with St Paul in 2000, it is now styled the Church of St Mary with St Paul.