Traditionally founded around the year 500 by Gwynllyw, Lord of Gwynllwg, (whose name has corrupted to Woolos). The present St Mary’s Chapel is said to be on the site of the original church, and retains some pre-Conquest masonry. Around 1080, a Norman nave of 5 bays was added. Around 1200, St Mary's chapel was raised in height. In the C15, following damage when Newport was razed by Owain Glyndwr, aisles were added, as well as a 2-storey S porch, and the W tower, known as the Jasper Tower, after Jasper Tudor, who was responsible for some of the work.
The church was restored 1818/19. In 1853, R G Thomas, architect, demolished the medieval porch and built a new one; and the chancel was rebuilt. In 1913, William Davies, architect, built vestry, and uncovered archaeological features. In 1960-62, the chancel was demolished and rebuilt, on a large scale by A D R Caroe, architect. The E window and mural were designed by John Piper, the mural being painted by scenery painters of Royal Opera House, Covent Garden. In the early 1990s, a hall was added on the N side. The Diocese of Monmouth was created only in 1921; St Woolos achieved full cathedral status in 1949.