Old English cirice, circe "place of assemblage set aside for Christian worship; the body of Christian believers, Christians collectively; ecclesiastical authority or power," from Proto-Germanic *kirika (source also of Old Saxon kirika, Old Norse kirkja, Old Frisian zerke, Middle Dutch kerke, Dutch kerk, Old High German kirihha, German Kirche).
This is probably [see extensive note in OED] borrowed via an unrecorded Gothic word from Greek kyriake (oikia), kyriakon doma "the Lord's (house)," from kyrios "ruler, lord," from PIE root *keue- "to swell" ("swollen," hence "strong, powerful").
Greek kyriakon (adj.) "of the Lord" was used of houses of Christian worship since c. 300, especially in the East, though it was less common in this sense than ekklesia or basilike. An example of the direct Greek-to-Germanic transmission of many Christian words, via the Goths; probably it was used by West Germanic people in their pre-Christian period.
The word also was picked up by the Slavic tongues, probably via Germanic (Old Church Slavonic criky, Russian cerkov). Finnish kirkko, Estonian kirrik are from Scandinavian. Romance and Celtic languages use variants of Latin ecclesia (such as French église, 11c.).
Phonetic spelling from c. 1200, established by 16c. For vowel evolution, see bury. After the Reformation, church was used for any particular Christian denomination agreeing on doctrine and forms of worship.
As an adjective, "pertaining to a church," from 1570s. Church-bell was in late Old English. Church-goer is from 1680s. Church-key "key of a church door" is from early 14c.; slang use for "can or bottle opener" is by 1954, probably originally U.S. college student slang. Church-mouse (1731) "a mouse supposed to live in a church" (where there is nothing for it to eat) is proverbial in many languages for poverty.