Lennel Kirk served the village of Lienhale, which once stood to the east of the graveyard but now no longer exists.

The small Lennel Kirk was constructed in the 1120s. The building was dedicated to St, Mary in 1243 by the Bishop of Durham. The foundations of the church are probably of Anglo-Saxon origins with the nave being medieval. The small church was added to over time.

Initially, the church held mass led by a priest, but after the Reformation, the church survived and switched to providing sermons held by a preacher. Lennel Kirk survived the Reformation, while nearby Coldstream Priory was destroyed. It continued to act as the parish church until 1705 when the population shifted to nearby Coldstream, and without a congregation, the church fell into disuse and then disrepair.

During the 18th and 19th centuries, the churchyard was the victim of body snatching. The oldest burials date back to the 15th century. The remains of the church were restored in 2017.