Melksham is a town on the river Avon lying 10 miles E of Bath and 6 miles W of Devizes; in the Middle Ages the town was surrounded by Melksham Royal forest. The church lies to the W of the town and consists of a chancel, nave, N and S aisles (the latter added in the 14thc), N and S chapels built in the 15thc, a Perpendicular clerestory, N porch added in the 15thc, and W tower. Inside the chancel the outlines of intersecting decorative arcades on the N and S walls indicate that the chancel dates from the 12thc. The S wall of the chancel features traces of a piscina. A billet stringcourse and the clasping shallow corner buttresses also indicate that it is Norman in date though it has been refenestrated with Perpendicular windows.

The church was possibly built on the site of a wooden Saxon church, of which no evidence survive. The Domesday Book records that in 1066 Earl Harold and Liseman had the lordship of 'Melchesha'; in 1086 Romuld, priest of Melksham, administrated the manor, which was held in-chief by King William. It was a large and valuable estate worth £113.6. In 1144 the Empress Maud granted the manor to Humphrey de Bohun III, which remained in his possession until 1157–8 when it was resumed by the Crown and assigned to Devizes Castle. In 1220 the church was granted to the Bishop of Salisbury and became a possession of the canonry of Salisbury Cathedral.

In form, and probably in terms of its decoration originally, the chancel seems to be related to St John the Baptist and St Mary the Virgin at Devizes. It may have had Norman vaults like these churches. This is suggested by breaks in the intersecting arcading and the strong corner buttresses.

The roof and the galleries were restored in 1810, but a larger restoration was carried out in 1845 by Thomas Henry Wyatt: the 16thc central tower was entirely rebuilt at the W end of the church, and a vestry was added to the N of the chancel; also, the galleries and the 15thc S porch were removed.