For centuries, the history and life of the parish church were interwoven with the life and work of the Benedictine Abbey of Our Lady and St Rumon, which lay immediately to the south of the present church.
The Abbey was built by Ordulf, Earl of Devon, and was completed in 981, when its charter was granted, but was looted and destroyed by Danish invaders in 997. After being rebuilt, the Abbey continued to function until the Dissolution of the monasteries throughout England in 1539.
The first fully authenticated reference to the Church of St Eustachius dates from 1265. St Eustachius was a Roman general in the second century who became a Christian. He was disgraced and exiled and was finally martyred with his family for refusing to sacrifice to the Roman gods. He is one of the fourteen Auxiliary Saints or Holy Helpers who are commemorated in particular at Vierzehnheiligen in Bavaria.
Only one other church in England is dedicated to St Eustachius but there are dedications in Rome, Istanbul and Paris and he is patron saint of Madrid. Icons of St Eustachius, the gift of a Greek Christian named Eustachius, have been given to the church.
Nothing of the 1265 church survives. A new church was built by Abbot Robert Champeaux (1285-1324) and was dedicated in 1318.
By the middle of that century, the church had fallen into disrepair and the chancel was without a roof. By the end of the century, the church had been largely rebuilt in the Perpendicular style, although a few traces of the 1318 church remain.
In the fifteenth century, some further rebuilding work took place, the main addition being the Clothworkers' Aisle, funded by a bequest from Constance Coffyn, the widow of three wealthy wool merchants of Tavistock and completed in 1447.
Churchwardens' Accounts of 1540 mention a clock and chimes with payment to a man to oil the clock. After several renewals, the present clock and chimes were given to the town, funded partly by public subscriptions but mainly by a generous donation from the Duke of Bedford. The clock, although located in the Tower, is the property of the Town Council. While repair work has been necessary from time to time, the same mechanism has been in use for many decades. The chimes have a melody for each weekday and at times these can be heard, beginning on Monday with "Auld Lang Syne", then "The Minstrel Boy", "The Bluebells of Scotland", "Ye Watchers and Ye Holy Ones", "The Church's One Foundation" and for Saturday, "Home Sweet Home". Two faces of the clock are illuminated at night and the other two are blackened stone with gold figures.
The church has had a ring of bells since at least the fifteenth century. It is recorded in 1423 that a new wood frame was provided and in 1470 the bells were "shifted" at a cost of five shillings. A new bell was purchased in 1574/5 and the "little bell" mended. These bells disappeared, perhaps being melted down, during the English Civil War (1642-1649). Eight bells of the present peal date from 1769, given by the 4th Duke of Bedford, they were cast by Thomas Bilbie of Cullumpton and were re-cast and re-hung in 1925 by John Taylor of Loughborough. Two hundredweight was added to the tenor bell. A treble and a second bell were cast by Taylors in 1998, being funded in part by the Millennium Commission, the rest being contributed by local people. The new bells were dedicated by the Bishop of Plymouth in December 1998.