Eesti Evangeelse Luterliku Kiriku Karja Katariina kogudus asutati juba 13. sajandil roomakatoliku kiriku Saaremaa piiskopkonna Karja kirikukihelkonnana. Karja kirikut – praeguse kirikuhoone eelkäijat – mainitakse esmakordselt juba 1254. aastal kui „Karja maaks“ nimetatud piirkonna kirikut. Praegune gooti stiilis rikkaliku skulpturaalse dekooriga kirikuhoone ehitati erinevatel hinnangutel kas 13. sajandi lõpukümnenditel või 14. sajandi algupoole.
Katoliiklikuna püsis Karja kogudus umbes 300 aastat – kuni 16. sajandi keskpaigani. Kihelkonna piiridesse jäi Püha Nikolause kabel Metskülas, mis 17. sajandil oli juba varemeis. Alates 1524. aastast ulatusid Martin Lutheri algatatud reformatsiooniliikumise mõjud ka Saaremaa piiskopkonda, ehkki diötseesi ametikandjad (piiskop, toomkapiitel) jäid vana usu juurde.
1562. aastal jõustas Taani kuningas Frederik II Saaremaal Taani luterliku kirikuseaduse. Hiljemalt siis said Karja koguduse usu- ja kirikuelu aluseks luterlikud põhimõtted, ent kõik muu jäi samaks – kihelkonna piirid, kirikuhoone, koguduseliikmed.
Kiriku püüdest rahvast usuliselt harida kasvas välja luterlik koolikorraldus. 1686. aastal andis Rootsi kuningas Karl XI käsu asutada igasse Eesti- ja Liivimaa kihelkonda talurahvakool. 18. sajandil oli ka Karja koguduse juures ametis koolmeister, allikate teatel oli alates 1760. aastate algusest olemas eraldi koolimaja. 1819. aasta talurahvaseadus nägi ette kaheastmelise koolisüsteemi – igas kirikukihelkonnas pidi olema kihelkonnakool ja igas vallas (mõisakogukonnas) üks madalama astme kool.
Patronaadiõigust ehk pastori ametisse nimetamise õigust omas Karja koguduses enne Põhjasõda Rootsi kuningas, pärast Vene alla minekut Venemaa keiser. Praktikas teostas kroonupatronaati kuberner. Koguduseelu majandusasjade juhtimisel andsid tooni kohalikud mõisavaldajad, kelle hulgast valiti teatud perioodiks eestseisja(d). Pastori korraldusi täitsid talupoegadest vöörmündrid ehk rotmeistrid, igast mõisapiirkonnast 1–2.
Karja kirikukihelkonna luterlik konfessionaalne ühtsus püsis omakorda ligikaudu 300 aastat. 19. sajandi keskpaigas siirdus aga umbes 38 protsenti Karja koguduse liikmetest õigeusku. Visitatsiooniprotokollide andmeil kaotas Karja kogudus võrreldes 1843. aastaga koguni rohkem kui pooled oma liikmetest – kui enne „äralangemist“ (Abfall) oli liikmeid 5299, siis 1851. aastal oli koguduses 2416 inimest, neist 972 meest ja 1444 naist.
Kirikuraamatud andmetega liikmete kohta on säilinud aastatest 1740–1763/64 (pastor J. G. Holmi ajast) ja alates 1834. aastast (pastor J. R. Hunniuse ajast). Enne 1920. aastate keskpaika peetud meetrikaraamatud asuvad Ajalooarhiivis Tartus ja on digiteeritud.
20. sajandil muudeti usuline kuuluvus inimeste eraasjaks. Kirik lahutati riigist ja ta kaotas oma kunagised eesõigused ja avalikud ülesanded. Kirikusse kuulumisest sai isikliku valiku küsimus. Aastal 2025 oli Karja koguduse liikmete loendis umbes 150 ristitud liiget. Juriidiliselt on kogudus MTÜ, millel on oma juhatus, nõukogu ja täiskogu.
Karja kogudusel oli 19. sajandist kuni teise maailmasõja järgsete aastateni abikirik Metskülas. 1874. aastal ehitatud Metsküla abikiriku või kabeli hoone on säilinud, ent ei ole enam Karja koguduse valduses.
Karja kogudust teeninud vaimulikke läbi aegade
KATOLIIKLIK KOGUDUS
- Johannes, surnud enne 27. II 1412
- Johannes Redtberch, mainitud 23. V 1519
- Mathias Braseken, mainitud 6. III 1520 (Püha Antoniuse altari vikaaria)
- Cornelius Schurs(en) de Dulken, surnud 1550 (?)
- Jodocus (Jobst) Monetarius (Monther), alates 5. III 1551
LUTERLIK KOGUDUS
- Berndt, mainitud 1567
- Christian(us) Tunder, 1591–1600 (?)
- Conrad(us) Sagittarius (Schütz), 1608–1649
- Christoph(orus) Schreiber, 1650–1666 (?)
- Heinrich Vulpius (Fuchs), 1669–1690
- Johann Georg Briegelius, 1690–1709
- Georg Martin Bürger (von Burguer), 1710–1739
- Johann Georg Holm, 1740–1763
- Daniel Bonge, 1764–1774
- Friedrich Wilhelm (von) Willmann, 1774–1819, adjunkt 1772
- August Gottfried Christian Hildemann, 1819–1838, adjunkt 1803
- Johann Reinhold Hunnius, 1838–1867, adjunkt 1833
- Reinhold Johann Winkler, 1872–1896, adjunkt 1867
- Karl Wöhrmann, 1896–1925
- Axel Fromhold-Treu, 1927–1937
- Hans-Joachim Eichhorn, 1937–1939, adjunkt 1936
- Arnold Voldemar Elken, hooldas 1940–1942
- Andres Põldmets, 1942–1947
- Oskar Leis, 1951–1974
- Toomas Paul, 1976–1986
- Jaan Tammsalu, 1988–1989, praktikant 1986, diakon 1987
- Gustav Kutsar, 1991–1993, diakon 1989
- Veiko Vihuri, alates 1993, diakon 1991
- Hannes Nelis, hooldas 1999–2000
