mid-14c., "of the doctrines of the ancient Church" (before the East/West schism), literally "universally accepted," from French catholique, from Church Latin catholicus "universal, general," from Greek katholikos, from phrase kath' holou "on the whole, in general," from kata "about" + genitive of holos "whole" (from PIE root *sol- "whole, well-kept").
Medieval Latin catholicus was practically synonymous with Christian and meant "constituting or conforming to the church, its faith and organization" (as opposed to local sects or heresies). With capital C-, applied by Protestants to the Church in Rome c. 1554, after the Reformation began. General sense of "embracing all, universal" in English is from 1550s. Meaning "not narrow-minded or bigoted" is from 1580s. The Latin word was rendered in Old English as eallgeleaflic.