Although St Mary's is in the centre of Stafford it stands in its own large close, reached through a narrow passage from Greengate Street, the main shopping thoroughfare on which St Chad's stands. The church is a large one, cruciform with transepts and an octagonal crossing tower that had a spire until 1594. The chancel has five-bay aisles, the N largely given oven to organ and vestry use, and the S a Lady Chapel. The nave is aisled too, with five-bay arcades and a clerestorey. The earliest fabric here is 13thc., and there is also Decorated and Perpendicular work, and the church was thoroughly restored by George Gilbert Scot in 1841-44. According to Pevsner's analysis, the nave and its arcades are early 13thc. work, although the crocket capitals are Scott’s. The W doorway and a plain N aisle doorway are also early 13thc., while the W window belongs to the later 13thc. The S aisle windows are 14thc. and the N aisle windows and clerestorey are Perpendicular. The S doorway and its porch are Scott's. As we move into the transept and chancel, Scott's work becomes more apparent, doubtless because when the spire fell in 1594, it fell eastwards. The N transept was not restored, and retains an early 14thc. N doorway and window, and a Perpendicular clerestory. Scott removed the clerestories in the chancel and S transept. Some 13thc. windows survive in these parts of the church, but most of the windows are Scott's. The only 12thc. feature is the Italianate font.

The Domesday Survey records a group of 13 canons in Stafford, described as the King's Prebendary canons, who owned 14 messuages in the town and 3 hides outside. The church was probably granted by Henry I to Jordan, clerk to Roger de Fecamp, and in 1136 King Stephen gave the churches of Stafford and Penkridge to the bishop and cathedrals of Coventry and Lichfield (then joint holders of the see). The gift was confirmed by the pope in 1139, 1144 and 1152, but was reversed by Henry II when he came to the throne and the churches reverted to the crown. Henry appointed William de C. and his successor Robert as the first known deans of St Mary's. A tradition that the college was founded by King John first occurs in the 16thc, but VCH suggests that if John was responsible for anything it may have been a new dedication to St Mary.

Pevsner describes the font as 'Norman and under Italian influence'; Fisher as 'undoubtedly foreign', but possibly carved by foreign workers in Stafford. Neither Bond nor Drake nor the present author has any doubt that it is English. Bond related the animal supports of the base to the fonts of Castle Frome (Herefords) and Elmley Castle (Worcs.). Drake compared the upper, lion base to that on the font at Shobdon (Herefords) and suggested that the lower, square base may be later than the upper base and the bowl, but still medieval. He also pointed out that the quatrefoil form of the bowl is commoner in Scandinavia than elsewhere. There is nothing to relate it to the present church, and it has been suggested (Fisher) that it may have come from St Chad's, where the present font is a neo-Romanesque piece made in 1856.

Wood (2016) offers the interesting suggestion that the font 'owes its unique features to the chance presence of a skilled designer, most likely a visiting foreign cleric', and speculates that 'the most obvious patron for the initiation of such activity would be Bishop Roger de Clinton, sometime after he acquired the collegiate church from King Stephen in 1136 and before his death in 1148.'