This event necessitated the building of a new church, which took a total of 120 years to complete, and was consecrated in 1238. The Norman tower was rebuilt in the Decorated Gothic style in about 1350, and the Perpendicular fan vaulting was added between 1496 and 1508.. In 1541, following the Dissolution of the Monasteries, the church survived by being selected as the cathedral of the new diocese of Peterborough. This may have been related to the fact that a former queen, Katherine of Aragon, had been buried there in 1536. Her grave can still be seen, and is nowadays honoured by visitors and often decorated with flowers. It carries the legend "Katharine the Queen", a title she was denied at the time of her death. In 1587, the body of Mary Queen of Scots was also buried here, but was later removed to Westminster Abbey on the orders of her son, King James I of England.
The cathedral was vandalised during the English Civil War. Almost all the stained glass was destroyed, and the altar and reredos were demolished, as were the cloisters and Lady Chapel. Some of the damage was repaired during the 17th and 18th centuries. In 1883, extensive restoration work began, with the interior pillars, the choir and the west front being completely rebuilt.