The earliest reference to the church occurs in a deed of Walter of Gloucester, datable to 1095. According to this deed, Walter granted two thirds of the tithes of Colesbourne church to the church of St Owen in Gloucester (Walker 1964). The presentation to the church appears to have belonged to the Loholt family, knightly followers of the earls of Hereford. Ellis Loholt is the earliest attested member of the family to hold lands in Colesbourne. By the early 1140s, Ellis appears to have been the principal lord of the manor. His descendant, Walter Loholt, granted the presentation of Colesbourne church to the Augustinian canons of Lanthony in the mid-1240s (VCH Gloucestershire).