Indications are that Heddon grew around the 12th Milecastle, on the southern side of Hadrian's Wall, close to the fort at Rudchester. After the departure of the Romans, Anglo-Saxon invaders from Northern Germany and Holland settled in the area and were responsible for building the original Church at Heddon.

After the Norman conquests of 1066 the land was given by Henry I to the Norman Barons. The six townships of Heddon parish were made up of Heddon on the Wall, East Heddon, West Heddon, Houghton, Whitchester and Eachwick. They were bestowed upon Hugh de Bolbec, whose family came from Bolbec, in Normandy, as a part of the Barony of Styford.

The Bolbec family established a monastry at Blanchland in 1165 and gave the rights and patronage of St Andrew's church in Heddon on the Wall to the monastry.

The name Heddon is thought to have been derived from "heath hill" or "place were heather grows". In earlier times it was also known as "Heddon Ad Murum". Ad Murum is simply the latin for "on the wall" or "at the wall".