The church consists of a chancel, nave, aisles, S porch, W tower and spire. The building dates from about 1175 when a stone church was built to replace an earlier structure on the site. The N aisle dates from the early 13thc., the S aisle was built in 1342, and the chancel was rebuilt by the Dean and Chapter of Lincoln in 1432. Restoration of the chancel was carried out in 1892, and subsequent restoration campaigns on the remainder of the building occurred in 1897, 1903 (porch) and 1912. Romanesque features are the S door to the chancel (c.1175) and blind arcading on the top storey of the tower.

The earliest church at Edwinstowe was reputedly built over the site of the temporary burial of St. Edwin, King of Northumbria after the battle of Heathfield in 632AD. A church and a priest is mentioned at Edwinstowe in the Domesday Survey when it is listed as part of the lands of the King being an outlying part of the Royal Manor of Mansfield. William II gave the church to the Dean and Chapter of Lincoln and it is mentioned in a Charter of 1146.