Perustettiin Limingan emäseurakunnan kappeliksi noin 1645 ja sai ensimmäisen oman kappalaisen 1655. Kirkko mainitaan jo 1647, jossa kuitenkin harvoin saarnattiin tuolloin, ja uusi kirkko rakennettiin 1664. Kirkonkokous Tyrnävän erottamisesta Limingasta itsenäiseksi pitäjäksi pidettiin 25.5.1888 ja päätös vahvistettiin keisarillisella käskykirjeellä 20.2.1889, jonka mukaan Tyrnävä oli erotettava Limingasta toisen luokan konsistoriaaliseksi kirkkoherrakunnaksi ja kirkkoherran palkaksi, Mankilan virkatalon, lisäksi määrättiin vähintään 8 500 markkaa. Seurakuntaan kuuluva Murron rukoushuone vihittiin 27.9.1908, jonka jälkeen täällä pidettiin jumalanpalveluksia joka toinen kuukausi. Tyrnävän kunta perustettiin 1865.
Muut nimet
Törnävä
Kylät
Ängeslevä, Tyrnävä
Naapuriseurakunnat
Papisto
Suostumus Tyrnävän, Limingan ja Lumijoen kappalaisten palkoista tehtiin 34.5.1735.
Kirkkoherrat
1901–1905 Adolf Castrén
1908– Petter Gustaf Korpi
Kappalaiset
1655–1692 Josephus Samuelis Lithovius
1692–1711 Jacobus Essevius
1712–1742 Johan Hedraeus
1744–1748 Georg Georgii Rajalin
1749–1764 Johan Forshäll
1764–1777 Kristian Henrik Keckman
1777–1795 Sven Olsbo
1797–1803 Gerhard Snellman
1806–1825 Per Junnelius
1827–1832 Anders Engelberg
1832–1852 Johan Henrik Hjulberg
1856–1876 Johan Peter Snellman
1880–1901 Adolf Castrén, virka lakkautettiin
Ylimääräiset papit
1726– Samuel Keckman, kappalaisen apulainen
1771– Henrik Enqvist, kappalaisen apulainen
1793– Erik Ganander, kappalaisen apulainen
1812–1815 Johan Vilhelm Holmberg, kappalaisen apulainen
1824–1825 Frans Isak Fortell, kappalaisen apulainen, vt. kappalainen
1825–1826 Ernst Vilhelm Frosterus, vt. kappalainen
1826–1827 Johan Zakris Cajaner, vt. kappalainen
1839 Kristian Vilhelm Litzell, kappalaisen sijainen
1839 Johan Leonard Gumerus, kappalaisen sijainen
1839–1840 Karl Fredrik Meurling, kappalaisen sijainen
1845–1848 Karl Nauklér, kappalaisen sijainen
1852–1855 Robert Mellin, kappalaisen apulainen, armovuodensaarnaaja
1852 Reinhold Helander, kappalaisen apulainen
1852 Jonas Kristian Castrén, virkavuodensaarnaaja
1855–1856 Gabriel Vilhelm Melart, armovuodensaarnaaja
1876–1877 Lars August Malmberg, virkavuodensaarnaaja
1877–1880 Johan Henrik Foudila, armovuodensaarnaaja
1878 Juho Tanskanen, armovuodensaarnaaja
1901–1902 Rurik Calamnius, kirkkoherran apulainen
1902 Johannes Jaakko Mustakallio, kirkkoherran apulainen
1904 Bror Gabriel Einar Borg, kirkkoherran apulainen
1904 Frans Felix Öberg, vt. kirkkoherra
1905–1906 Niilo Iisakki Simelius, armovuodensaarnaaja
1906–1908 Bror Gabriel Einar Borg, vt. kirkkoherra, armovuodensaarnaaja
Arkisto
Tyrnävän seurakunnan rippikirjat alkavat vuodesta 1703, tilikirjat vuodesta 1669 ja historiakirjat syntyeiden osalta vuodesta 1822, vihittyjen osalta vuodesta 1832 ja kuolleiden osalta vuodesta 1825. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1607–1939.
Seurakunnan kirkko hävitettiin murhapoltolla 24.11.1865, jolloin suurin osa arkistoa tuhoutui, esimerkiksi rippikirjat vuosilta 1714–1726, 1740–1780 ja 1812–1832 sekä syntyneiden luettelot vuoteen 1822, vihittyjen luettelot vuoteen 1832 ja kuolleitten luettelot vuoteen 1825. Seurakunnan pappila paloi perustuksiaan myöden 20.10.1931, mutta arkisto säilyi tuholta. Tuli tuhosi kirkon sisustan 14.2.1960 ja palossa eniten kärsivät alttari ja kirkkosalin lattia penkkeineen.
Kansallisarkisto on digitoinut Tyrnävän seurakunnan vanhimmat kirkonkirjat noin 1860-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.