The origins of St Mary's are lost in time, but it is probable that by the late 9th century a wooden Saxon church existed here. The first stone church may well have been built in the reign of Edward the Confessor; there is mention of a church in the Domesday Book (1086). The present building was largely the work of the later 14th century, following on the arrival in Beddington of St Nicholas Carew in the 1350s. He united the two manors which had existed since Saxon times, and for the next five centuries the church and the village were closely connected with the fortunes of the Carew family. Apart from stylistic changes at the time of the Reformation, and the creation of galleries in the 18th century, the fabric of the church was hardly touched until the 19th century, by which time it had fallen into some disrepair. Between 1829 and 1869, a number of significant structural changes took place, including repairs to the tower, the addition of the Nicholas or north chapel, the vestries and the internal decorative work.