The church was originally founded in 1123 by Roger de Newburgh, Earl of Warwick. He designated the church as a Collegiate church.

There is an impressive surviving crypt with rib-vaulted arches. Those at the east end date from the 14th century, probably related to the time that the chancel was rebuilt by Thomas Beauchamp. It was finished by his son in 1392. It has panels with unusual flying ribs and contains the tomb of Thomas Beauchamp, died 1369. To the north of the chancel is the vestry, with the sacristy above.

The mediaeval Saint Mary's had a nave and aisles with a western tower, with north and south transepts, which remain much the same today. Off the south transept is the Beauchamp Chapel, begun in 1443. It was completed in 1464, and cost £2481 to build. It was originally detached from the chancel, but is now linked via the Dean's Chapel. It contains the tomb of Richard Beauchamp, died 1439. There are also monuments to Robert Dudley, Earl of Leicester, died 1588, and also to Robert Dudley, Lord Denbigh died 1584 aged three. Also a monument to Ambrose Dudley, Earl of Warwick, died 1590, and other monuments. The east window was originally by John Prudde from the 15th C. The Chapel was vandalised by Puritan troops in 1643, and restoration work began soon after.

The 14th century chapter house sits on the north side of the chancel and contains a monument to Fulke Greville, first Lord Brook who died in 1628.

The nave, aisles, transepts and tower were destroyed in the Great Fire of Warwick in 1694, and rebuilt by 1704 by Francis and William Smith to designs by Sir William Wilson, possibly with help from Sir Christopher Wren. The west tower is 174 foot high and visible for miles around. Pevsner calls it "curiously tired". It arises sheer from the pavement above an open arch. It was restored in 1885. Inside, the aisles are the same height as the nave, with all three spaces vaulted and slender piers with capitals of acanthus leaves. The most western piers are considerably more massive than the others, showing that the tower was originally meant to be built there. In fact it was started but abandoned due to cracks appearing.

The north transept has been set aside as the Regimental chapel of the Royal Warwickshire Regiment. The south transept originally housed the tomb of Earl Thomas 12th Earl of Warwick (d.1401) and his wife Margaret Ferrers (d.1407), parents of Earl Richard, 13th Earl of Warwick. This was destroyed during the fire

There is a large organ with four organ cases in different positions around the church.

There is a selection of stained glass from mediaeval through to modern glass from 2001. Many of the nave windows are clear.