The Domesday Book records that by 1086 Sir John Maltravers held the manor of Lytchett Matravers.

The John Matravers who was buried in the church was Edward II's gaoler and possibly his murderer.

A Sir Walter Maltravers went on a Crusade to the Holy Land and it is possible that he ordered the church to be built beside the manor house in his absence about the year 1200.

There is also an unusually large hagioscope or squint giving a view from the north aisle to the chancel and altar.

The church slowly fell into disuse and was used solely by the Rector for morning prayer and vespers, with regular worship moving to a chapel in the village.

A great deal of restoration was carried out at the beginning of the 16th century at the behest of Dame Margarita Clements.

In the 17th century the Arundel family, heirs by marriage to the Maltravers estate, funded the restoration of St Mary's and rebuilding of the north aisle.

In the English Civil War, Parliamentarian infantry defaced a tomb in the north aisle, removing and destroying its inscribed plaque.

The north transept was extended in 1993 to give added facilities including a new vestry and small upper room which was used for Sunday school and some meetings.

The joists that support the floor under the chancel step were found to be rotten due to moisture created by the problem with the walls.

Other structural and maintenance problems were addressed in the years 2012–13, including re-digging of soak-aways to help the drainage and drying of the church and a significant number of minor and medium-priority issues that were highlighted in the 2010 quinquennial report.