Kuului alkuaan Salon emäseurakuntaan, josta erotettiin omaksi pitäjäksi ja itsenäiseksi kirkkoherrakunnaksi 1573. Seurakunnassa oli alkuaan saarnatupa kunnes varsinainen kirkko rakennettiin 1610 (tai 1620). Kirkkoa pidennettiin 1689. Pappilan huoneita mainitaan rakennetun jo 1587. Karlön eli Hailuodon vapaaherrakunta annettiin läänityksenä eversti Berndt Taubelle 1652 ja se peruutettiin kruunulle 1675. Kirkko kärsi suuria vaurioita isonvihan aikana. Kirkkoa korjattiin 1739, 1756 ja 1847. Hailuodon kunta perustettiin 1865.
Muut nimet
Carlö, Karlö, Luoto
Maakirjakylät
Kirkonkylä, Ojakylä, Kello
Naapuriseurakunnat
Papisto
Kirkkoherra sai kruununkymmenyksiä neljä puntaa viljaa kuninkaan kirjeellä 12.6.1589 ja myöhemmin vastikejyviä 12 tynnyriä. Papin palkasta tehtiin suostumus 3.2.1735. Kirkkoherralle maksettavista kalakymmenyksistä Keisarillisen senaatin päätös 16.1.1862. Kirkkoherran vastikejyvät 19,8 hehtolitraa viljaa peräytettiin Keisarillisen senaatin päätöksellä 22.5.1897. Kappalaisen virka yhdistettiin kirkkoherran virkaan Keisarillisen senaatin päätöksellä 17.1.1908.
Uuden palkkausjärjestyksen 22.5.1897 mukaan maksettiin manttaaliin pannuilta tiloita yhteensä 115,47 hehtolitraa rukiita, 115,47 hehtolitraa ohria sekä 1154 markkaa 70 penniä rahaa, jotka jaettiin seurakunnan hyväksymän äyrityksen mukaan. Palkka jaettiin palkansaajien kesken siten, että kirkkoherra sai kaksi kolmasosaa ja kappalainen yhden kolmasosan. Kutakin 2 566 äyriä kohden siis suoritettiin kirkkoherralle kolme litraa rukiita, kolme litraa ohria ja 30 penniä rahaa sekä kappalaiselle 1 1/2 litraa rukiita, 1 1/2 litraa ohria ja 15 penniä rahaa.
Kirkkoherrat
1587–1603 Thomas Laurentii Paldanus
1604–1615 Ericus Henrici Frosterus
1616–1617 Henricus Erici Frosterus
1618–1625 Marcus Amundi
1625–1646 Sigfridus Canuti
1648–1672 Marcus Jacobi Salovius
1672–1698 Henricus Sigfridi Björnholm (Ijoensis)
1698–1707 Gustaf Forselius
1708–1717 Samuel Julenius
1718–1724 Alexander Kranck
1724–1735 Simon Solinius
1795–1804 Jonas Cajanus
1805–1809 Johan Pettersson
1812–1839 Erik Johan Frosterus
1840–1857 Gustaf Adolf Saxbäck
1858–1876 Karl Robert Heikel
1877–1883 Emil August Wichmann
1883–1895 Niilo Karlsberg, ensin vt. kirkkoherra
1896–1901 Johan Adolf Snellman
1903–1906 August Alfred Simola
1907–1909 Juho Abram Pietola
1910–1920 Eino Virkkula, nimitettiin virkaan 1909
1920–1927 Juho Kustaa Saarento
1928–1930 Eero Juhani Ahola
1933–1936 Einari Hohti
1938–1944 Svante Tolonen
1944–1952 Antti Jalmari Pulkkinen
Kappalaiset
1627–1639 Josephus Josephi Palman (Caslenius)
1654–1672 Henricus Sigfridi Ijoensis (Björnholm)
1672–1694 Johan Marci Salonius (Salmenlius)
1694–1698 Gustavus Erici Forselius
1700–1712 Henricus Hackman
1713 Anders Cajanus, nimitettiin, mutta ei astunut virkaan
1724–1735 Anders Mathlin (Matilainen)
1736–1769 Frans Mikael Allgen
1761 Petrus Kjellin
1761–1764 Abraham Schroderus
1763–1801 Gabriel Lagerberg
1803–1823 Johan Vilander
1826–1846 Israel Reinhold Petterson
1849–1851 Johan Gabriel Lagus, ensin vt. kappalainen
1851–1860 Jakob Arvid Frosterus
1862–1870 Karl August Snellman
1870–1873 Karl Alfred Calamnius
1877–1880 Josef Salem Laurell
1881–1892 Nils Viktor Nordlund
1894–1896 Kaarlo Matti Huovinen
1898–1906 Paavo Hyttinen, ensin vt. kappalainen, virka lakkautettiin
Apupapit ja armovuodensaarnaajat
1800–1806 Jakob Åhlgren, kappalaisen apulainen
1807 Isak Petterson, kirkkoherran apulainen
1809–1812 Johan Pettersson, kirkkoherran apulainen, virka- ja armovuodensaarnaaja
1823–1826 Johan Vilhelm Holmberg, virka- ja armovuodensaarnaaja
1857–1858 Oskar Elis Petterson, kappalaisen apulainen
1876–1877 Josef Salem Laurell, sijaiskirkkoherra, kirkkoherran ja kappalaisen viran välisaarnaaja
Ylimääräiset papit
1893–1894 Kaarlo Matti Huovinen, vt. kappalainen
1897 Juho Kustaa Lammi, vt. kappalainen
1906–1907 Eino Virkkula, vt. kirkkoherra, vt. kappalainen
1909–1910 Bror Gabriel Einar Borg, vt. kirkkoherra, armovuodensaarnaaja
1910 Richard August Hjelt, vs. kirkkoherra
1927–1928 Fras Josef Bergh, va. kirkkoherra
1930–1932 Väinö Akseli Näyhä, vt. kirkkoherra
1936 Urho Veli Väinämö Pyy, vt. kirkkoherra
1937–1938 Toivo Aulis Voutilainen, vt. kirkkoherra
1943 Ano Emil Kauppinen, vt. kirkkoherra
1944 Veikko Kumpulainen, vt. kirkkoherra
Arkisto
Hailuodon seurakunnan rippikirjat alkavat vuodesta 1890, tilikirjat vuodesta 1702 ja historiakirjat syntyneiden osalta vuodesta 1721, vihittyjen osalta vuodesta 1772 ja kuolleiden osalta vuodesta 1702. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1702–1915.
Seurakunnan vastavalmistunut pappila paloi 2.8.1901, jolloin tuhoutuivat vanhimmat rippikirjat vuoteen 1890 saakka sekä joukko muita asiakirjoja. Kirkkoherra Johan Adolf Snellman kuoli silloin sydänhalvaukseen. Tuhoutuneet asiakirjat luetellaan 11.9.1901 laaditussa katselmuspöytäkirjassa, jonka mukaan palossa tuhoutuivat vuonna 1818 lahjoitettu pitäjän sinetti teräksestä, käsikirja vuodelta 1757, rippikirjat vuosilta 1751–1890, lastenkirjat vuosilta 1881–1890, vihittyjen luettelot vuosilta 1812–1896, syntyneiden luettelot vuosilta 1840–1892, muuttaneiden luettelot vuosilta 1841–1897, aviokuulutusten luettelot vuosilta 1843–1896, kuninkaallisten kollegioiden ja maaherran käskyt ja muut vastaavat 1896–1745, pitäjän- ja kirkonkokousten pöytäkirjat vuosilta 1812–1819 ja 1831–1853, tilikirjat kirkon varoista vuodesta 1831 sekä katovuonna 1832 pitäjään asetetun vaivaiskomitean pöytäkirjat ja muut asiakirjat.
Kansallisarkisto on digitoinut Hailuodon seurakunnan vanhimmat kirkonkirjat säilyneiltä osin 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.