Hiiumaa jagati XIII sajandi keskel Liivi ordu ja Saare piiskopkonna vahel. Tagasivaatena meenutame, et Pühaleppa alustati ordu poolt kivikiriku ehitamist üsna kohe peale maade jagamist ja juba sajandi lõpuks oli ühelööviline, kaitseotstarbeline kirik valmis.
Saare piiskopkonna maadel nii kiiresti asjad ei kulgenud. Piiskopkonna keskuseks kujunes Käina. Tuntud kirikuhoonete uurija, arhitektuuriajaloolane Villem Raam on arvanud, et esialgne Käina kirik võidi ehitada ligikaudu samal ajal kui Pühalepa, ehk siis XIII sajandi teisel poolel, kuid puust. 1981. aastal tehtud arheoloogiliste uurimuste käigus leiti vanad puidufragmendid ja mõned XIV sajandi mündid, mis seda arvamust kinnitasid. Täpsemalt selle kohta aga andmeid ei ole.
Käina puitkirik eksisteeris ligi 200 aastat, kivikirik ehitati piiskop Johannes Orgiesi käsul (ametis aastatel 1492-1514). Ilmselt ei olnud Käinas väliseid vaenlasi niipalju karta kui Pühalepas ja kaitsekirikuks vajadus puudus. Tõenäoliselt ehitati gooti stiilis kirik 1500. aasta paiku, igatahes toimus Käina kivikirikusse 1522 aastal piiskop Johanees Kyveli visitatsioon.
Ühelöövilise kiriku müürid ehitati paekivist, paeplaatidega kaeti ka põrand. Idaosas asuv kooriruum oli ristvõlvitud. Põhjaküljel on väike käärkamber. Kuna pinnas kiriku all oli savine ja ebakindel ning kirik hakkas vajuma, siis ca 150 aastat hiljem, 1660 aastat paiku rajati kiriku nurkadesse massiivsed tugisambad. Lääneseinas kõrgus sale kivitorn, mida parandati ja uuendati XVIII sajandi keskel. Kirik oli pühitsetud pühale Nikolausele. Kirikus asus kuni selle hävimiseni Nikolause puitkuju, mis oli ligikaudu sama vana kui kirik isegi.
Kiriku katoliiklikust ajajärgust palju teada ei ole. Üsna peatselt peale kivikiriku ehitamist toimus reformatsioon ja ka Käina kirikust sai pühale Martinile pühitsetud luterlik kirik. Kihelkond oli üsna suur, kuni 1866. aastani kuulud Käina kiriku alla ka Emmaste piirkond. Hiiumaa kirikute patroon krahv Axel Julius De la Gardie Käina kirikule üsna suure maatüki, mille tagajärjel sai Käina kogudus suurima maaomandiga (ligi 600 ha) kirik Eestis. Loomulikult andis see olulise sissetuleku kohalikule õpetajatele. Hiljem, Emmastesse iseseisva koguduse tekkimisel vähenes nii koguduseliikmete arv kui ka õpetajate sissetulek.
Tuntumatest õpetajatest Käina kiriku ajaloos võib nimetada Tunderite „dünastiat“ Aastatel 1682 – 1760 olid Käina kirikus õpetajateks Otto tünder, teme poeg Samuel Tunder ja viimase poeg Friedrich Wilhelm Tunder. Neile järgnesid Rootsi päritolu Albert Magnus Haller ja tema poeg Jacob Pontus Haller. Albert Magnus Haller asutas 1786 aastatl Käina kihelkonnas esimese külakooli, kus lapsed talveperioodil kuus päeva nädalas õppisid. Mõned aastad hiljem oli koole juba kolm – Suure-Lelus, Kaigutsis ja Seljal, hiljem lisandus veel Putkaste. Kuigi vahepeal toimus koolitöös taandareng, jätkas hiljem ametis olnud õpetaja Georg Friedrich Ignatius, keda rahvas hüüdis Naatsuseks, kooliharidese andmist, rajades Käinasse spetsiaalse leerikooli. Leeri läbimiseks, samuti abiellumiseks oli lugemisoskus kohustuslik.
Käina koguduse ajalukku kuulub kahtlemata ka Tobiase pere. Isa Johannes (1847-1909) oli Käina kiriku köster. Ka tema isa Peeter teenis Käina kirikus köstrina. Johannes oli muusikaliselt andekas, tal oli ilus lauluhääl. Lisaks sellele oli ta orelimeister ja klaverihäälestaja. Ka Käina kiriku orel oli Johannes Tobiase ehitatud. Muide, see orel on kujutatud Eesti 50-kroonisel rahatähel, mille esiküljel on Rudolf Tobiase portree, tagaküljel aga Käina kiriku oreli prospekt. Tõenäoliselt on ka Mänspäe kabelis olev mängukõlbmatu ja rüüstatud orel Johannes Tobiase kätetöö. Tobiaste perre sündis 13 last, neist teisena 1873. aastal Rudolf Tobias, kes omandas esimese eestlasena professionaalse muusikalise hariduse helilooja ja organistina. Rudolfi lapsepõlv möödus Käinas, oma esimese muusikalise hariduse sai ta isalt, siin tegi ta 9-aastase poisina ka esimesed katsetused heliloomingu vallas. Kuigi pere kolis 1884. aastal Kullamaale, Rudolf alustas õpinguid Haapsalu koolis ja hiljem Tallinnas ning Peterburis, elutee lõppes aga Saksamaal, oleme hiidlastena Rudolf Tobiast „oma“ heliloojaks pidanud. Käinas on Tobiaste majamuuseum, tema nime kannab ka Kärdla muusikakool.
1859-1860 ehitati Käina kirik põhjalikult ümber. Kiriku lõunasein lammutati ja sinna ehitati juurdeehitus, mis asetseb risti vana pikihoonega. Altar tõsteti ringi põhjaseina ning juurdeehitusele tuli uus peauks. Algselt lääneküljes oleva peaukse kohal olnud piiskop Orgiese vapitahvel tõsteti ümber uue ukse kohale. Läänepoolse ukse kohale müüriti aga XVII sajandist pärit, paekivist valmistatud rõngasrist, mis on samal kohal tänini. Selline põhja-lõuna suunaline kirikupaigutus oli Baltimaades ainulaadne. Juurdeehitise valmimise järel oli Käina kirik oma 600 istekohaga Hiiumaa suurim
Teise Maailmasõja lahingute jõudmisel Hiiumaale hävis Käina kirik tules. Kirikut tabas Saksa lennukilt heidetud süütepomm, mis kukkus läbi kooriruumi lae ja süütas kiriku. Väidetavalt oli kiriku torni kasutanud Vene tulejuhid. Kes seda enam täpselt teab, kuid üks Hiiumaa pühakodadest hävis täielikult. Tulle jäid ka paljud kunstiväärtused, muu hulgas varem mainitud, XVI sajandist päris püha Nikolause kuju.
Nõukogude võim teadagi ei soosinud kirikute taastamist, seega jäigi kirik varemetesse. Kollektiviseerimise ajal, 1949. aastal rajati Käinasse kirikuvaremete kõrvale Masina-Traktorijaam (hilisem EPT), mille alla jäi suurem osa kiriku juures olnud kalmistust. Kirikuvaremeid on kasutatud kütuselaona, millalgi sooviti müüride vahele rajada koguni tantsuplats. 1981. aastal teostati varemete juures arheoloogilisi uuringuid, jõudumööda on varemeid ka konserveeritud. Kirikupark ning kirikumüüride alla rajatud väike lava on olnud paigaks ka paljudele kontsertidele, teiste hulgas on seal esinenud paljud kristlikud lauljad ja koorid.
Eesti Vabariigi taasiseseisvumisest alates on EELK Käina Püha Martini kogudus otsinud võimalusi kiriku taastamiseks. Kahjuks osutuks see väga kalliks ja siiani ei oleks selleks võimalusi olnud. 2004. aastal sai uue kimmikatuse kooriruum, 2015 aastal said ukseavad suletud sepisvõredega. Ka varemetes on toimunud kontserte.
Käina kiriku varemed on märgiks sellest, millistest aegadest on meie rahvas pidanud läbi minema.