Ashby St Mary has origins in the late Anglo-Saxon period and is recorded in DB as Ascebei. The settlement comprised 29 households, placing it among the larger settlements recorded in Norfolk. The manor was divided between the holdings of Roger Bigot and Godric the Steward following the Norman Conquest. Local tradition suggests that the site may occupy the location of a Roman signalling station and that the church stands on earlier Saxon foundations, although the present fabric provides no clear evidence for either claim.
The chancel is largely a 13thc enlargement of the church. It retains lancet windows in the N and S walls and a priest's doorway in the S wall. The W tower was added during the 15thc and includes a stair turret at the north-east corner. The S porch is largely of late medieval date and incorporates Tudor brickwork. Within the church, evidence for the medieval roof structure survives in the wall plates. The tower arch has been lowered, although the original responds retain carved lion corbels.