Alkuaan Muolaan emäseurakunnan kappeli, jollaisena mainitaan ainakin 1728. Eräälle Vuoksen saarelle rakennettiin rukoushuone 1745, jossa Muolaan papisto piti jumalanpalveluksia joka kolmas sunnuntai. Seuraava kirkko rakennettiin mantereelle 1772 ja tätä kirkkoa kunnostettiin 1821. Seurakuntaan asetettiin oma kappalainen keisarin käskykirjeellä 22.6.1843. Erotettiin Muolaasta itsenäiseksi kirkkoherrakunnaksi keisarin käskykirjeellä 14.1.1868. Uusi kirkko rakennettiin tiilestä ja vihittiin käyttöön 2.10.1881. Heinjoen kunta perustetiin 1869.
Heinjoen kunta luovutettiin kokonaisuudessaan Neuvostoliitolle 19.9.1944 solmitun välirauhansopimuksen mukaan ja kunnan toiminta loppui vuoden 1948 kuluessa Suomen eduskunnan säätämän lain mukaisesti (Suomen asetuskokoelma 486/1948). Heinjoen seurakunta lakkautettiin ja kaikkien luovutettujen alueiden seurakuntien toiminta päättyi 31.12.1949, jonka jälkeen niin sanottujen siirtoseurakuntien luterilaiset jäsenet kirjattiin asuinpaikkakuntansa seurakunnan kirkonkirjoihin. Vuoden 1945 maanhankintalain mukaisen sijoitussuunnitelman mukaan Heinjoen asukkaat sijoitettiin Vihtiin, Pyhäjärvelle, Nummelle, Karjalohjalle, Sammattiin, Pusulaan ja Karkkilaan.
Kylät
Heikurila, Hentula, Hevossaari, Kääntymä, Kämärä, Koprala, Kurvila, Lahdenperä, Lapinlahti, Pienpero, Pihkala, Pilppula, Pirilä, Rättölä, Ristseppälä, Savastila, Tuokkola, Vamppala
Naapuriseurakunnat
Papisto
Heinjokelaiset velvoitettiin ilman emäseurakunnan apua palkkaamaan kappalaisensa ja rakentamaan kirkkonsa sekä rakentamaan kappalaisensa virkatalon, mitä vastaan heidät vapautettiin velvollisuudesta rakentaa Muolaan emäseurakunnan kirkkoa ja kappalaisen virkataloa keisarin käskykirjeellä 13.10.1864. Kappalaisen palkasta kirkonkokouksen päätökset 18.9.1842 ja 14.1.1844 sekä vahvistus 11.11.1848.
Uudessa palkkausjärjestyksessä 3.2.1893 säädettiin, että "Jos uudessa veronlaskussa manttaalien lukumäärä seurakunnassa muuttuu, on uusi jako kaikkien pappispalkkausta silloin maksavien manttaalien välillä tehtävä sillä tavoin, että vanhain manttaalien maksusumma tasoittuu uusille manttaaleille". Tilalliset suorittivat vanhan tavan mukaan kirkkoherralle kultakin manttaalilta heiniä 700 kiloa, rukiinolkia 300 kiloa sekä halkoja 18 kuutiometriä, puoleksi koivu- ja puoleksi mäntypuita. Kirkkoherralla oli oikeus kalastaa nuotalla seurakunnan kaikissa kalavesissä ja käyttää eläimiään kaikilla karjalaitumilla seurakunnassa.
Kirkkoherrat
1868–1886 Karl Adolf Streng
1890–1905 Pekka Sormunen
1907–1920 Paavo Pakkanen
1921–1925 Martti Savelainen
1926–1928 Ilmari Sirén
1929–1950 Kustaa Palovaara
Kappalaiset
1844–1863 David Eklund
1864–1868 Karl Adolf Streng
Ylimääräiset papit
1845–1847 Johannes Hertz, kappalaisen apulainen
1858 August Magnus Tolpo, kappalaisen apulainen
1859–1862 Fredrik Vilhelm Brander, kappalaisen apulainen
1862–1863 Alexis Kniper, kappalaisen apulainen
1863 Peter Malinen, armovuodensaarnaaja
1864 Karl Adolf Edvard Vinter, armovuodensaarnaaja
1886–1889 Oskar Vilhelm Weisman, vt. kappalainen
1889–1890 Pekka Sormunen, vt. kirkkoherra
1905–1907 Paavo Pakkanen, vt. kirkkoherra
1920–1921 Bruno Kunnala, vt. kirkkoherra
1925–1926 Paavo Lehtinen, vt. kirkkoherra
1928–1929 Urho Valtari, vt. kirkkoherra
Arkisto
Heinjoen seurakunnan rippikirjat alkavat vuodesta 1774, tilikirjat vuodesta 1820 ja historiakirjat vuodesta 1822. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Mikkelissä ja aineistokokonaisuus kattaa vuodet 1774–1950.
Seurakunnanan vanhimmat rippikirjat vuodesta 1774 siirrettiin Muolaan kirkonarkistosta 1874. Vuotta 1822 vanhemmat historiakirjat lukeutuvat Muolaan kirkonkirjoihin.
Seurakunnan lakkauttamisen jälkeen sen arkisto siirrettiin evankelis-luterilaisen kirkon keskushallinnon alaiseen Lakkautettujen seurakuntien keskusarkistoon (LSKA), jossa asiakirjoihin tehtiin merkintöjä vuoteen 1990. LSKA liitettiin Mikkelin maakunta-arkistoon 1990.
Kansallisarkisto on digitoinut Heinjoen seurakunnan kaikki kirkonkirjat. Yli 100 vuotta vanha aineisto on vapaasti tutkittavissa Astia-palvelussa. 100 vuotta nuoremmat aineistot ovat käytettävissä kaikissa Kansallisarkiston tutkijasaleissa ja niiden käyttäminen edellyttää tutkimusluvan hakemista.