Arvatavasti oli esimene, 13. sajandil rajatud, kirikuhoone Käinas puidust.

15. saj lõpus, 16. saj alguses oli Saare-Lääne piiskopiks Johannes III Orgas (1420-1515). Lääneportaali kohal asus Orgase vapikivi ja kuna kiriku seina võis oma atribuute müürida vaid hoonet rahastanud metseen, siis dateeritakse kirikuhoone ehitus aastatesse 1493-1515.

Rajati hilisgooti stiilis ühelööviline saalkirik. Hoone (algne) põhiplaan on ristkülikukujuline: pikihoone, ruudukujuline kooriruum. Koori põhjaküljes eendub hoonest käärkamber.

17. saj tekkisid seoses kiriku aluseks oleva viirsavi pinnase vajumisega ning läänefassaadi ümberehitustöödega kiriku müüridesse ohtlikud vertikaalpraod. 1660 päästeti kirik laialivajumise eest läänefassaadi külge ja idafassaadi nurkadesse rajatud massiivsete tugipiilaritega. Toestustööde patrooniks oli Axel Julius de la Gardie (1637-1710).

1752. aastal ehitati endise lagunenud torni asemele uus kivist torn, 36 m kõrge. Juba 1789. aastal kurdeti, et torn vajab väljastpoolt parandamist ja on viltu. Sama on olukord praegu. Rõngasrist lääneportaali kohal on 16. saj-st (üks vanemaid Eestis), tehtud Kaarma paekivist

Kooriruumis käärkambri uksest idapoole jääb põrandalt algav nišš, mida sildab ümarkaare sillus. Kooriruumi idaseina põhjapoolses osas maapinna lähedal asub veel üks nišš – tabernaakel, seda kaunistas polükroomne ehiskivi. Kooriruum ja käärkamber on kaetud roieteta ristvõlvidega. Koori lõunafassaadil on ainuke hoonel originaalkujul säilinud teravkaarne gooti aken.

Kooriruumi põrand oli kaetud paeplaatidega (hauaplaadid)

Käärkambri loodenurgas on olnud kamin.

Pikihoones oli 1936. aasta teate järgi puitpõrand. Põhjaküljes algselt aknaid ei olnud.

Kirikus olid lisaks peaaltarile altarid Maarjale, Antoniusele ja Nikolausele. Varsti pärast kivikiriku valmimist paigaldati kirikusse umbes pooleteist meetri kõrgune Püha Nikolause (algne kiriku kaitsepühak) puidust skulptuur, mis hävis kiriku põlengus 1941. aastal.

Viimane suurem ehitustegevus kiriku juures toimus 1859 – 1860, mil seninekirikuhoone oli kihelkonnarahvale kitsaks jäänud. Lisati lõunatiib, seejuures lammutati pikihoone lõunafassaad. Pärast ümberehitust oli kirikus 600 istekohta. Lõunaportaali kohale paigaldati piiskop Orgase vapikivi, selle kohal on väike paekivi, kuhu on raiutud 1860. Lõunatiiba rajati ka uus peasissepääs, mille vastu pikihoone põhjaseina paigutati altar (see on ainulaadne lahendus, üldjuhul paikneb altar kiriku idaseinas). Kiriku põhjaseina tehti kaks ümarkaarset aknaava, ka kooriruumi gootipärane idaaken tehti laiemaks ja ümarkaarseks.

1930 olla kirikuhoone olnud suhteliselt halvas olukorras, mistõttu 1935 koostati kiriku hädaremontimise eelarve. 1936 oli remont valmis.

14. oktoober 1941 tabas kirikut saksa lennuki süütepomm, kuna kirikutorni kasutati saksa sõdurite pihta tulistamiseks. Tules hävis kogu inventar, puidust katuse- ja laekonstruktsioonid, muuhulgas ka Rudolf Tobiase isa, köster Johannes Tobiase, ehitatud orel.

Pärast II maailmasõda kasutati varemeid naftalaona, lasketiiruna, toornahkade vastuvõtupunktina, välirestoranina, lauluväljakuna.

2024 toimusid kirikuvaremetes taastamistööd. Lõunaportaal taastati algses suuruses, selle kohale asetati taas piiskop Orgase vapikivi, portaali ette said sepisväravad. Kindlustati hoone lõunatiiva aknakaared edasise lagunemise eest. Tööd teostas OÜ RestHunt.