Valjala kihelkond ulatus viikingiajal Saaremaa põhjakaldasse välja. 13. sajandil loodi siin iseseisev Karja kihelkond. Võimalik, et esimene kirik asus Karja mõisa juures ning ehitati saarlasest mõisaomaniku poolt juba enne maa ametlikku ristiusustamist. 1254. a. lepiti kokku piir Liivimaa ordu ja Saare-Lääne piiskopi haldusala vahel. Karja jäi piiskopile ja Pöide ordule. Praeguse kivikiriku ehitus algas 1280. aasta paiku või pisut hiljem. Karja Katariina kirik ehitati kõrgemale kohale, mis asus enam-vähem võrdses kauguses suurematest küladest ning võis olla piirkondlik kogunemiskoht.
Kirik võis valmida mõne aastaga. Kunstilisi sarnasusi leidub siin Paderborni toomkirikuga, mille ümberehitus jõudis lõpule 13. sajandi teises pooles. Karja mõisa surnuaialt leitud münt vermiti just sel ajal Paderbornis. Karjas töötanud meistrid on ametis olnud ka Muhu ja Pöide kirikus, samuti Tallinna toomkirikus ja Boge kirikus Ojamaal.
Torni pole Karja kirikul kunagi olnud. Palverändurite majutamiseks ehitati käärkambri peale kaminatuba. Eriliseks teeb kiriku rikkalik raiddekoor, milles on kujutatud kohalikke mehi ja naisi. Võidukaare külgedel on pühakud Katariina ja Nikolaus. Seintel ja lael on maalingud, mis sisaldavad põnevaid sümboleid. Näiteks on siin kolmjalg ehk triskele Jumala kolmainsuse tähenduses. Aastal 2022 andis Eesti Pank välja kullast meenemündi, millel kujutatud rist pärineb Karja kirikust.
1345. aasta talvel tuli orduvägi Saaremaale Jüriöö ülestõusu maha suruma ja peatus Karjas kaheksa päeva. Kui ümbrus oli paljaks rüüstatud, palusid saarlased rahu. Karja kiriku lääneuks sai nii tugevasti kannatada, et müüriti hiljem kinni. Vigastused lõunaukse ümber on tänaseni näha. Karja kiriku ristimiskivi pärineb 14. sajandist, kuid selle jalg võib olla vanem. Väike puust krutsifiks on Karja kiriku altaril juba 15. sajandi lõpust saadik. Katoliku ajal ehitati kirikust 20 km kaugusele Metskülla püha Nikolause kabel.
1559. a. müüs Saare-Lääne piiskop oma valdused Taani kuningale. Järgmisel aastal saabus Kuressaarde kuninga vend, hertsog Magnus, kes kuulutas enda Saare-Lääne piiskopiks. Olles rahahädas, müüs ta 1567. a. Karja kirikuõpetajale kolm talupoega. Ligikaudu sel ajal ehitati kiriku lõunaküljele eeskoda. 1638. a. valmistas Kuressaare meister Balthasar Raschky Karja kiriku praeguse kantsli.
1645. a. läks Saaremaa Rootsi koosseisu. Karja õpetaja Heinrich Vulpius esindas Saaremaad 1686. a. piiblitõlke konverentsil Liepas. Luuletusi kirjutas Vulpius nii ladina, kreeka kui saksa keeles. Tema surma järel teenis Karja kogudust väimees Johann Georg Brigelius. Vulpiuse teine väimees, Johann Christoph Röser teenis Kihelkonna kogudust. Mõlemad väimehed surid Põhjasõja aegse katku ajal.
Usklike mõisahärrade kaudu jõudis vennastekoguduse ärakamine varakult Karja kihelkonda. Ärkamisest olid haaratud nii Laugu, Parasmetsa kui Koikla omanikud, kuid talurahva hulgas liikumine laiemat kandepinda ei leidnud. Pärast seda, kui Georg Martin Bürger 1739. aastal kirikuõpetaja ameti maha pani, kutsuti Karja kogudust teenima vennastekoguduse-sõbralik Johann Georg Holm. 1748. a. käis ta vennastekoguduse kohta aru andmas. Õpetaja Holmilt nõuti, et ta edaspidi sellele liikumisele vastu seisaks. Holmi surma järel saabus uus hingekarjane naaberkogudusest – Daniel Bonge oli juba Saaremaa Jaani koguduses tuntuks saanud vennaste liikumise veendunud vastasena.
Karja pastoraat aina lagunes. Aastal 1767 võttis koguduse juhatus kätte ja kirjutas keisrinna Katariinale – kes oli muuhulgas ka Karja kiriku patroon – palve, et kõigi venelaste isevalitsejanna ja suur proua paneks aru pähe Karja kihelkonna mõisnikele, kes ei tahtnud panustada pastori elumaja ehitamisse. Seda, kas kõrgemalt poolt ka raha saadi, ei ole teada, kuid pastoraat ehitati juba samal aastal üles. Viis aastat hiljem käskis keisrinna Katariina viia kõik surnuaiad eluhoonetest vähemalt 600 meetri kaugusele. Nii lõpetati ka Karja kirikusse ja selle ümber matmine ning rajati praegune surnuaed. Seejärel müüriti kinni kiriku põhjapoolne uks ja tehti taas lahti läänepoolne.
Daniel Bonge viimastel aastatel oli talle abiliseks väimees Friedrich Wilhelm Willmann, kellest sai tema mantlipärija Karja kirikuõpetaja ametis. Willmann avaldas trükis jutlusi ning 1782. a. ilmus „Juttud ja Teggud“, mis on vanim säilinud eestikeelne ilmalik juturaamat. Lisaks koostas ta kristliku kombeõpetuse „Ellamisse-Juhhataja“ ja saksakeelse mesilastepidamise käsiraamatu. 1781. a. lasi ta Karja kirikule teha uue altariseina ja 1790. a. tõsteti õpetaja Willmann aadliseisusesse.
Ka Willmanni tööd jätkas tema väimees, õpetaja August Gottfried Christoph Hildemann. 1820. aastate algul ehitati Metskülla puust kabel, kus kirikuõpetaja käis aeg-ajalt jumalateenistust pidamas. Kahjuks polnud õpetaja Hildemann suuremat asja jutlustaja. See-eest sündis 1823. aastal Karja kihelkonna Ratla külas üle Saaremaa tuntud ilmikjutlustaja Aleksander Toom, kes kõneles paljudes paikades, eriti Valjala ja Kaarma kiriku juures.
Rudolf Kallas sündis 1851. a. küll Kaarmal, kuid tema vanemad olid pärit Karja kihelkonnast: isa Leisi taluperest, ema oli aga Karja köstri Redik Allase tütar. Mõnda aega õppiski Rudolf Kallas oma onu, Karja köster Carl Allase juures.
Kui Karja koguduse õpetaja Johann Reinhold Hunniuse tervis ei lubanud enam ametit pidada, jätkas tööd tema väimees Reinhold Johann Winkler. Aeg ei olnud kerge. Kolmandik suurest kihelkonnast oli läinud üle õigeusku. 1873. a. ehitati Leisi õigeusu kirik, hiljem ka Pärsama ja Metsküla kirikud. Nii sai Karja kihelkonda sarnaselt Pöidega kokku kolm õigeusu kirikut.
Mihklipäeval 1873 tegi kange tuulemaru Metsküla vanale puukabelile otsa peale just jumalateenistuse ajal. Järgmise aasta maikuus hakati samale kohale kivikabelit ehitama. Koolmesiter Toomas Rand kogus annetusi. Paekivid kinkis Metsküla mõisaomanik von Sass. Ehitusel oli Toomale abiks tema naisevend Priidu Uussaar koos mõne palgatud töömehega. Oktoobris pühitses kabeli Karja koguduse õpetaja.
1882. a. ehitas Gustav Normann Karja kirikule oreli ja kirikusse ehitati rõdud. 1883. a. põles maha õpetaja elumaja. Tuli sai hakatuse korstnast lõuna ajal. Uuel aastal püstitati uus kivist hoone. 1887. a. valmis Karja kiriku praegune altarisein Peterburi arhitekt Franz Gienckeni kavandi järgi. Altarit kaunistab koopia Guido Reni maalist „Kolgata“. Õpetaja Winkler suri Karja kiriku kantslis Meie Isa palvet lugedes. „Vaid päästa meid ära kurjast…“ jäid tema viimasteks sõnadeks. Kui pastor käärkambrisse kanti, hakkas kogudus nutma nii, et kirik mühas. Kuni uue pastori valimiseni teenis kogudust Winkleri väimees, Valjala õpetaja Eugen Blossfeldt.
Sakslastest mõisnikud valisid uueks hingekarjaseks eestlase Karl Wöhrmanni. Ta oli tubli põllumees, rahvamees ja vaimulik kirjamees. „Kiriku Laulu- ja Palveraamatus“ on tema sõnad lauludel „Valgus koidab, valgus paistab“ ja „Ma tunnen oma Jeesust“. Kui Esimese maailmasõja ajal jäi Saaremaale ainult viis kirikuõpetajat, oli tööd palju. Rahvas ütles: „Olgu ilm missugune tahes, Karja õpetaja oma kollasega (võik hobune) on ikka teel.“ Kuna Esimese maailmasõja ajal viidi Karja kiriku kell minema, kinkisid rootslased 1926. aastal uue. Aasta varem lõpetas rootsi ajaloolane Helge Kjellin restarureerimistööd Karja kirikus. Muuhulgas tehti siis rõdud kiriku külgedel lühemaks ja muudeti kantsli asukohta.
Õpetaja Axel Treu pidi tervislikel põhjusetel ametist loobuma. Teda raviti Tallinna Seevaldi haiglas. 1939. aastal läks ta Saksamaale, kuid jäi seal teadmata kadunuks. Saksamaale läks ka õpetaja Joachim Eichhorn. Õpetajad Tõldsepp ja Elken põgenesid Rootsi. Nõukogude võimu survel muudeti Metsküla kabel viljakuivatiks. Kui õpetaja Andres Põldmets 1947. aastal suri ja kirikuõpetaja ei jõudnud lumetormi tõttu kohale, pidas matuse kohalik õigesu preester. Seejärel pidas Karja kirikus jumalateenistusi jutlustaja Mihkel Paugus.
Uue kirikuõpetaja sai Karja kogudus 1951. aastal. Oskar Leis oli küll ilma kõrghariduseta, kuid sügavalt usklik inimene, kes ustavalt täitis oma ülesandid: kuulutas Jumala Sõna ja remontis kirikut. Pärast õpetaja Leisi surma teenisid Karja kogudust Valjala vaimulikud. Diakon Jaan Tammsalu ristis ja leeritas 1987. aastal Karja kirikus 19-aastase Veiko Vihuri, kes neli aastat hiljem ise Karja kogudust teenima tuli. Karja kihelkonnale truuks jäänud õpetaja Vihuri pole ennast kunagi tagasi hoidnud ei kirjasõna ega interneti vahendusel, vaid on talle omase otsekohesuse ja tulisusega võidelnud väärnähtuste vastu kirikus ja ühiskonnas, nahutanud sõnadega nii ülemaid kui alamaid, toimetanud veebiväljaandeid, joonistanud karikatuure, pidanud praosti ametit, kaitsnud doktoriväitekirja ja seisnud alalhoidlike väärtuste ning pühakirjakeskse õpetuse eest.
