Lieksan sekä Pielisniemen ja Pielissalon kylät kuuluivat Ilomatsin pogostaan 1500. Lieksa mainitaan Ilomantsin ortodoksisen seurakunnan kappelina 1589. Lieksan luterilaiset kylät määrättiin liitettäväksi Liperin kappeliin 1638 mutta nämä kylät erotettiin kuitenkin itsenäiseksi kirkkoherrakunnaksi 1639. Koko pogostaa läänityksenä hallinnut kreivi Per Brahe perusti vuonna 1653 Lieksanjoen suulle Brahean kaupungin, jonka venäläiset hävittivät 1656. Jälleenrakennettu kaupunki oli olemassa noin vuoteen 1680 saakka ja taantui myöhemmin kirkonkyläksi.
Venäläiset ryöstivät seurakunnan kirkon isonvihan aikana 1712 vieden saaliin Kajaaniin, jossa se uudestaan ryöstettiin. Vuonna 1765 rakennettu kirkko ja kellotapuli paloivat ukkosentulesta 14.8.1828. Uusi kirkko rakennettiin 1833–1838 ja vihittiin käyttöön 1840. Kirkossa pääsi tuli irti 13.5.1911 mutta palo saatiin sammutettua.
Seurakuntaan kuulunut Nurmeksen kappeli erotettiin itsenäiseksi kirkkoherrakunnaksi 1810 ja Juuan kappeli 1873. Seurakuntaan perustettiin Viekijärven rukoushuonekunta 1907 ja se erotettiin itsenäiseksi kirkkoherrakunnaksi 1948. Viekijärvi liitettiin Pielisjärven seurakuntaan ja seurakunnan nimeksi tuli Lieksa vuoden 1973 Pielisjärven ja Lieksan kuntajaon mukaisesti. Lieksan kaupunki perustettiin 1973.
Muut nimet
Lieksa
Maakirjakylät
Hattusaari, Hattuvaara, Höntönvaara, Jaakonvaara, Kitsinvaara, Kivivaara, Koli, Kontiovaara, Kuorajärvi, Kylänlahti, Lieksa, Louhivaara, Mukavaara, Nurmijärvi, Ohtavaara, Pankajärvi, Polvijärvi, Ruuna, Salo, Savijärvi, Siikavaara, Sikovaara, Sokojärvi, Uusikylä, Varpanen, Vieki, Viensuu (Vedensuu), Vuonislahti
Naapuriseurakunnat
Papisto
Papiston palkasta tehtiin suostumus 1754, joka vahvistettiin 19.8.1755. Kirkkoherran virkatalon metsän myynnistä saadut varat käytettiin suoviljelyksen edistämiseksi ja kansakoulun hyväksi Keisarillisen senaatin päätöksellä 18.2.1863. Päivätöistä keisarin päätös 11.7.1741. Kappalaisen voisaatavista Keisarillisen senaatin päätös 19.8.1880.
Kirkkoherrat
1639–1650 Thomas Jacobi
1652–1657 Anders Cajanus
1659–1688 Lauritsa Laurinpoika Hallitius
1689–1710 Petter Herkepæus
1723–1729 Joakim Niklaanpoika Clewe
1731–1738 Johan Pomoelius
1740–1766 Jakob Stenius vanhempi l. Korpi–Jaakko
1768–1809 Jakob Stenius nuorempi l. Koski–Jaakko
1812–1828 Jakob Abraham Strömmer
1834–1837 Johan Henrik Wahlsten
1840–1877 Johan Stenius
1878–1885 Oskar Grönholm
1887–1896 Samuel Porthan
1897–1916 Alex Fredrik Hahl
1918–1925 Ernesti Kyander
1925–1938 Kaarlo Johannes Korpitie
1939–1940 Emanuel Kolkki
1941–1954 Kristian Tammio
Kappalaiset
1676–1700 Marcus Wendalius
1702–1719 Georg Wallius
1723–1769 Erik Lackman
1770–1803 Johan Lackman
1804–1806 Jakob Vallgren
1808–1823 Samuel Fredrik Montin
1826–1836 Filip Hellenius
1839–1841 Herman Fredrik Forsberg
1843–1877 Gregorius Aminoff
1879–1886 Johan Pöyhönen
1887–1918 Ernesti Gustaf Kyander
1901–1939 Emanuel Kolkki, toinen kappalainen
1918–1925 Kaarlo Korpitie
Pitäjänapulaiset
1848–1854 Klas Veisell, persoonallinen pitäjänapulainen, kirkkoherran apulainen
Ylimääräiset papit
1650– Lauritsa Laurinpoika Hallitius
1730-luvulla Erik Lackman, papiston apulainen
Carl Salenius, papiston apulainen
1732–1735 Henrik Lindenius, papistonapulainen
1797–1804 Jakob Vallgren, kappalaisen apulainen, kirkkoherran apulainen
1799– Martti Joh. Lyra, kappalaisen apulainen
1801–1812 Johan Mårten Strömmer, kirkkoherran apulainen, armovuodensaarnaaja
1805–1809 Adam Melèn, kappalaisen apulainen, virka- ja armovuodensaarnaaja
1825–1826 Fredrik Polón, kirkkoherran apulainen
1826–1828 Gustaf Gabriel Bonsdorff, kirkkoherran apulainen
1828–1835 Johan Kristian Agander, kirkkoherran apulainen, välisaarnaaja
1835–1836 Zakarias Adolf Kroijerus, kirkkoherran apulainen
1836–1839 Gustaf Adolf Hillebrand, kirkkoherran sijainen, armovuodensaarnaaja
1838–1841 Elias Samuel Nymalm, kirkkoherran sijainen, kappalaisen sijainen
1840–1842 Johan Fredrik Niloni, kirkkoherran apulainen
1841–1843 August Wilhelm Krogerus, kappalaisen sijainen, kirkkoherran apulainen
1842–1843 Henrik Konstantin Corander, kirkkoherran apulainen
1844–1848 Johan Jakob Strömmer, kirkkoherran apulainen, vt. kappalainen
1848–1850 Jeremias Laurinus, kirkkoherran apulainen
1850–1852 Erik Saurèn, kirkkoherran apulainen, vt. kappalainen
1854–1855 Johan Varèn, kirkkoherran apulainen
1854–1860 Johan Viktor Johnsson, kappalaisen apulainen, -sijainen
1855–1856 Johan Teodor Dahlström, kirkkoherran apulainen
1856–1858 Johan Immanuel Bergh, kirkkoherran apulainen
1858–1865 Bengt Ivar Stenius, kirkkoherran apulainen, -sijainen
1862–1871 Mikael Adolf Pelkonen, kappalaisen sijainen, kirkkoherran sijainen
1872–1875 Erik Johan Stavèn, vt. kirkkoherra, vt. kappalainen.
1875 Johan Henrik Ilvonen, vt. kirkkoherra, vt. kappalainen
1876–1880 Viktor Johan Gabriel Krogerus, vt. kirkkoherra
1875–1879 Paavo Martikainen, vt. kappalainen
1885–1886 Jaakko Adolf Veijola, virka- ja armovuodensaarnaaja
1886–1887 Juho Sidensnöre, armovuodensaarnaaja, vt. kappalainen
1886–1887 August Mömmö, armovuodensaarnaaja
1887–1890 Antti Adolf Gummerus, kirkkoherran apulainen
1890–1892 Johannes Castrèn, kirkkoherran apulainen
1892 Tahvo Puhakka, kirkkoherran apulainen
1893 Heikki Niiranen, kirkkoherran apulainen
1894–1895 Paavo Antti Moberg, kirkkoherran apulainen
1895–1897 Karl Konstantin Aalto, kirkkoherran apulainen, armovuodensaarnaaja
1897–1900 Ernesti Kyander, kirkkoherran sijainen
1897–1899 Pekka Hyttinen, armovuodensaarnaaja
1899 Juho Kustaa Tyrni, armovuodensaarnaaja
1899–1900 Emanuel Lamppu, armovuodensaarnaaja
1900–1901 Akseli Kytö, kappalaisen apulainen
1901 Juho Hotinen, kappalaisen apulainen
Arkisto
Pielisjärven seurakunnan rippikirjat alkavat vuodesta 1723, tilikirjat vuodesta 1768 ja historiakirjat vuodesta 1689. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Joensuussa ja aineistokokonaisuus kattaa vuodet 1658–1960.
Kansallisarkisto on digitoinut Pielisjärven seurakunnan vanhimmat kirkonkirjat noin 1890-luvulle saakka ja aineisto on vapaasti tutkittavissa Astia-palvelussa. Suomen Sukuhistoriallinen yhdistys (SSHY) on digitoinut seurakunnan nuorempia kirkonkirjoja. Alle 125 vuotta vanhojen aineistojen tutkiminen vaatii kirjautumisen yhdistyksen jäsensivuille.