The church is built on the site of what was the cathedral of the Bishop of Crediton in the former diocese until 1050 when the see was transferred to Exeter.

A college of canons remained at Crediton, administering the buildings and life of the "collegiate" church.

The cathedra, the bishop's throne, was moved to Exeter in 1050, where it was placed in a Saxon minster until a purpose-built cathedral could be constructed which did not happen for many years.

Crediton had lost the see, but the Bishop of Exeter retained his palace there (a little to the north-east of Holy Cross) and his lands around the town.

The construction of a Norman church on the present site was started—building work was in progress in the 1130s—and a collegiate church (based on the old cathedral and initially staffed by eighteen canons with eighteen vicars) was established, although lack of funds meant that the number of canons was soon reduced to twelve.

The collegiate church was always completely secular: none of the canons or vicars lived the communal life of monks, their work being funded by income from tithes on the extensive lands of the parish (which were shared with the bishop).

John de Grandisson, Bishop of Exeter (1327–1369), attempted to ensure that at least the chief officers of the college, the precentor and the treasurer, were resident in the immediate area of the church.

The bequest of that testator, and others of around the same time, brought enough money for a complete rebuilding of the nave and chancel areas, which started in the early years of the fifteenth century.

Shortly afterwards the parishioners of Crediton entered into successful negotiations with the Crown for the purchase of the collegiate church which was then threatened with demolition.