A Saxon wooden church stood at the present site a thousand years ago, but was burnt down in 1074.Robert D'Oyly, the Norman Constable of Oxford, then built a single aisle chapel to replace the wooden church. Subsequently, Saint Hugh, the Bishop of Lincoln, rebuilt the church in 1194. His work can still be seen at the east chancel wall and the south aisle, as well as the altar dedicated to St Thomas Becket. A century later the scholars of newly founded Balliol College had an oratory dedicated to St Catherine in the present north aisle; and in 1320 the Carmelites founded a chapel in the south aisle, preserved as a unified piece to form the present Lady Chapel. Work on the tower began in 1513 and continued during the upheavals of the Reformation; some of the stones of Rewley Abbey, Oxford's Cistercian monastery, strengthened the base of the tower. In 1841–42, George Gilbert Scott, then young and unknown, rebuilt the chancel and the north aisle. This complemented his Martyrs' Memorial just north of the church. It was the first Victorian Gothic interior in Oxford.
Worship at St Mary Magdalen's is in the high, Anglo-Catholic tradition. Mass is celebrated 15 times per week: twice daily on weekdays, and three times on Sundays. The principal celebration is at 10:30 am on Sunday mornings.