Saint Andrews Church is located opposite the Swan Inn and parts of it date back to 680 AD (Saxon). The oldest parts of Saint Andrew's are still visible in some of the walls of the chancel behind the choir stalls. The original stone structure was built using recycled stone from Hadrian’s Wall. Before Saint Andrews church was built it is believed that the site was used for pagan ceremonies so the location has always been of religious significance.
A little more info about the church can be found here Northumberland Communities - Heddon-on-the-Wall.
Text adapted from Heddon-on-the-Wall From Wikipedia
Old photo of St Andrews Church from around 1909