Tradition holds that Paulinus, first Archbishop of York, founded a church here in 627 while baptising converts in the River Trent. Whether or not that legend captures something true, by 956 the site was important enough that King Eadwig granted land at Southwell to Oskytel, Archbishop of York, for a minster church. Most of what stands today began in 1108 when the Normans started rebuilding. They began at the east end so the high altar could be used as soon as the masonry rose, dismantling the Anglo-Saxon church as they worked west. Many older stones were reused, and a small tessellated floor and an eleventh-century carved tympanum in the north transept are all that remain visible of the Saxon building. By about 1150 the nave was complete, with seven bays of short circular columns, scalloped capitals, semicircular arches, and small round-headed clerestory windows above. It is severe and architecturally pure Romanesque, the most complete and unaltered Norman nave in England.

The original Norman chancel was square-ended and too small. The thirteenth century rebuilt it in the new Early English Gothic style between 1234 and 1251, and then in 1288 the Minster's masons added an octagonal chapter house off the north-east corner. The Leaves of Southwell, as the carved foliage is now universally known, run around the entryway and across the interior capitals. What sets them apart is botanical realism. The plants are not stylised acanthus borrowed from Roman precedent; they are species you could pick from any English hedgerow today. Buttercups have five petals, hawthorn has thorns, oak leaves have the right number of lobes, ivy curls the right way. Several Green Men, those mysterious leaf-spilling faces that appear in churches across medieval Europe, peer out from the foliage with vine springing from their mouths. The vault is in the Decorated Gothic style, but the stonecarving inside it is more daring than the architecture, and the result is the closest thing thirteenth-century Europe produced to botanical illustration.

Southwell Minster has been damaged repeatedly and somehow always patched up. During the English Civil War, after the third siege of Newark, Charles I surrendered to a Scottish Presbyterian army camped at Southwell in May 1646. The Minster's nave was reportedly used to stable cavalry horses, and the adjoining Archbishop's Palace was almost completely destroyed, partly by Scottish troops and partly by local people stripping it for lead and stone. Only the Great Hall of the palace survives as a ruined shell, visible from the south transept. On 5 November 1711, Guy Fawkes Night, the south-west spire was struck by lightning. The resulting fire spread through the nave roof, the crossing, and the tower, destroying the bells, the clock, and the organ. The repairs by 1720 gave the nave its flat panelled ceiling. In 1805 the spires themselves had to be removed because they threatened collapse. Ewan Christian, a Victorian church architect, rebuilt them between 1879 and 1881, and the pyramid silhouette returned to the skyline. The medieval rood screen, dating from about 1320 to 1340, came through it all unharmed and remains an outstanding example of the Decorated style.

For most of its life Southwell was a collegiate church rather than a cathedral, governed by sixteen prebendaries who held estates around the diocese of York. In August 1540, Henry VIII proposed making it the seat of a new diocese for Nottinghamshire and Derbyshire, but the scheme fell through. The minster was dissolved in 1548, restored by Philip and Mary in 1557, and operated for nearly three more centuries under statutes drawn up by Elizabeth I in 1579. Cathedral status, when it finally came, arrived 344 years after Henry first suggested it: the Diocese of Southwell was created in 1884 and the minster officially became a cathedral. In 1927 the diocese was divided, with Derbyshire moving to the new Diocese of Derby. The chapter house leaves continue to draw scholars and visitors, the Norman nave continues to look almost exactly as it did under Henry II, and the great Angel Window by Patrick Reyntiens, installed at the west end in 1996, brings a piece of late-twentieth-century stained glass into conversation with seven centuries of older work.