The church was built in the early 12th century on the site of an earlier building, possibly the ancient chapel of St Aaron that was known to have existed as a private chapel for the nearby Llantarnam Abbey. The church was dedicated to the Blessed Virgin Mary & Mary Magdalene, on her feast day, 22 July 1179. The church was also referred to the Monastery of Deuma throughout much of its history. In the 15th century significant alterations were made to the church and major reconstruction commenced, with the eastern wing renovated. Larger windows were installed at this time to provide more light to the aisles. A north chapel, believed to have been built using Italian marble altar reredos from Llantarnam Abbey, was erected, and was later referred to in 1535 as the "chapel of St Michael near the monastery".[1] The tower is of the Tudor architectural style, built of two stages in local stone, and the chancel arcade and stone arches in the early Renaissance shape appear to have been added in the early 16th century.[1][2]
In the 16th century, the poet Sawnder Sion, also known as the "Lion of Llantarnam", of Llantarnam Abbey was buried beneath the choir in the church,[3] witnessed by Dafydd Benwyn, another poet and friend of Sion who wrote a poem mentioning the bed "In the choir of St Michael".[1] During the "Popish Plot", on Sunday 17 November 1678, John Arnold of Monmouthshire captured Father David Lewis, also known as Charles Baker, at St Michael's Church where he was preaching; he was later executed.[4] The register of the church dates to 1727, when it is recorded that the church was a vicarage and "net yearly value £108, with 21 acres of glebe, in the gift of the Bishop of Llandaff".[1]
The church was renovated in 1869–70 by the architect E. A. Lansdowne.[2] A 6-acre cemetery was added in 1892, costing £3,100. In 1921, the church was again renovated, this time with significant changes to the walls by removing the plasterwork. A number of fine mediaeval murals were uncovered during the renovation, amongst them Elijah in the wilderness, John the Baptist and a depiction of a mediaeval priest.[1]