The castle of Eldbotle was built on a motte by John de Vaux in the 12th century (at a similar time he built Castle Tarbet on the nearby island of Fidra). The de Vaux family were Norman knights and came from Rouen in northern France. The castle is mentioned in two charters from between 1153 and 1162, and a third charter probably dating from late in the reign of William I (1165-1214).

By the first half of the 13th century the family had moved to their newly-built castle at Dirleton, and Eldbotle presumably fell into disrepair and ultimately obscurity. The site of it is traditionally said to be in Eldbotle Wood, although nothing is now visible.