Hiiumaa vanimaks kirikuhooneks ja üleüldse vanimaks säilinud hooneks Hiiumaal on Pühalepa kirik. Kiriku ehitamise ajendiks sai Hiiumaa jagamine Saare piiskopkonna ja Liivi ordu vahel, mis toimus 1254. aastal. Üsna koheselt alustati ordule kuuluvatel aladel kiriku ehitamist ja arvatakse, et esimese etapina valminu ehitati eeldatavasti 1255 -1260, pikihoone seinad pärast seda ja kirik võlviti umbes 1300. a paiku.
Miks kiriku kohaks valiti just Pühalepa, on teadmata. Hiiumaa elanikkond oli tol ajal ilmselt üsna väike, veel paar sajandit varem on Hiiumaad kohta kasutatud nimetust insula deserta, tühi saar. Vaevalt, et XIII sajandi keskelgi elanikkond kuigi suur oli. Nimi „Pühalepa“ viitaks justkui hiiele või mõnele pühale puule, sellest pajatavad ka mitmed kiriku ehitamisega seotud rahvalood, kuid täpset infot selle kohta ei ole. Üheks asukoha valiku põhjenduseks võis olla lähedalasuv Valipe maalinn, mis oli ordu tugipunktiks. Eks ka kirik oli otsekui maamärk, mis näitas ristiusu ja orduvõimu saabumist saarele.
Laurentsiusele pühitsetud kirik koosnes XIII sajandil ühelöövilisest pikihoonest ja kitsamast neljanurgelisest kooriosast. Esialgselt kirikul torni ei olnud. Kirik täitis kaitsekiriku funktsiooni, olles ordule sõjaliselt kindlustatud tugipunktiks. Algselt olid kiriku aknad vaid lõunaseinas ja need olid väga kitsad. Kirikus on kaks müüritreppi, üks kooriosas, teine pikihoones. Kooriruumi võlvide pealne oli aga ehitatud kaitseruumiks, kus orduvennad ja nende vasallid võisid rünnaku puhul varju leida.
Kiriku varasemast perioodist pärineb ka puidust valmistatud kappaltar, mis on dateeritud aastaisse 1460-1470 ja mille autoriks peetakse Tallinna tuntud kunstniku Michael Sittowi isa Clawes van der Sittowit. Haruldusena on säilinud ka kooriruumi põhjaseinal olev nn. Pühitsusrist, mis kirikut 1979. aastal uurinud kunstiteadlase Villem Raami sõnul on originaalne ja pärineb ligikaudu aastast 1300.
Liivi sõja ajal korraldasid Haapsalus peatunud Vene väed Hiiumaale rüüsteretke ja 1575.a. purustati kirik täies ulatuses. Ülalmainitud altar säilis rusude vahel imekombel. Kirik ehitati taas üles XVII sajandi alguses juba luterlikuna. Kooriruumi ristvõlvid taastati, pikihoone aga kaeti madalama puitlaega. Hiiesaare mõisnikud Gentschiedenid kinkisid 1636. aastal kirikule kivikantsli, mille raius dolokivist välja Haapsalu kiviraidur Joachim Winter. See kantsel on kogu Eestis ainulaadne. Kantslit kannab turjal evangelist Markus, tal on käes raamat ja jalge ees lõvi.
XVII sajandil pandi alus ka kellatornile. Suuremad ümberehitused toimusid 1760-1770 pastor Johann Chaleniuse ajal. 1770. aastal lisati tornile kolm korrust. Käärkambrit on esmakordselt mainitud 1805. aastal.
Oma lõpliku kuju sai kirik 1860. -1863, mil kirik ehitati pseudogooti stiilis ümber, laiendati aknaid ja lisati need ka põhjakülge. Tornikuppel valmis aastal 1874.
Aastate jooksul on kirikut teeninud kümned erinevad õpetajad, mainida tahaks neist aga kahte. Üks pikema staažiga vaimulikke Hiiumaal oli Pühalepa kirikut aastatel 1822 – 1880 teeninud Alexander Wilhelm von Sengbusch, kelle eluaastad olid (1796 – 1883). Hiidlased kutsusid teda Senkpussiks. Temast liikus rahva hulgas hulganisti naljalugusid, kuid tegemist oli tõsiuskliku mehega, kes hilisematel eluaastatel tõlkis vennastekoguduse kirjandust. Sengbusch asutas Pühalepas mitmeid pühapäevakoole, mille eesmärk tollal oli eelkõige lugemise ja kirjutamise õppimine.
Liusaks sellele oli Sengbusch aktiivne murdesõnade ja rahvalike lugude koguja ning koostas tänaseni osaliselt säilinud Pühalepa kirikukroonika. Oma viimased eluaastad veetis Sengbusch Saaremaal, kus tal oli kombeks taluperedesse sisse astuda ja jutlustada.
Teine tähelepanuväärne õpetaja oli Hendrik Kokamägi. Ta sündis 1884 . aastal Taageperas, õppis 1904-1910 Helsinkis luterlikus misjonikoolis ja ordineeriti 1910 misjonäriametisse. Teenis misjonärina Hiinas 1911-1917, puhkenud Hiina revolutsiooni tõttu pidi sealt lahkuma. 1919 tuli Kokamägi koos perega tagasi Eestisse ja 1920 valiti Pühalepa koguduse õpetajaks.
Kokamägi oli äratusmeelne mees, kelle jutlustamise stiil oli elav ja erinev teiste õpetajate omast. Peatselt hakati nädala sees pidama palvetunde, kuus hakati inimesi kutsuma eestpalvele ja rõhutati uuestisünni tähtsust.
Hendrik Kokamägi sai teenida kirikus vaid kaks aastat. 1922. aasta aprillis kirjutas ta konsistooriumile, paludes end „oma südametunnistuse hääle pärast“ kiriku teenistusest vabastada. Hiljem elas Kokamäe pere paar aastat Laukal, tema peetud palvekoosolekud said alusepanijaks Lauka baptistikogudusele.
1924. aastal Hiiumaalt lahkudes alustas Kokamägi tööd Briti ja Välismaa piibliseltsi Eesti esindajana ja piiblidepoo juhatajana, ja liitus Evangeeliumi Kristlaste kogudusega. Tema elust on tütar Taimi Proos kirjutanud raamatu „Südametunnistuse pärast. Hendrik Kokamägi elust ja tööst.“
Nõukogude aeg jättis oma jälje ka Pühalepa kirikule. Valitsev ateistlik ilmakord püüdis kirikuid sulgeda ja otsis selleks erinevaid põhjusi. 1951. aastal kirik rekvireeriti ja muudeti ETKVL jahulaoks. Pingid lõhuti välja ja jahukotte laadides sõideti hobuvankriga kiriku peauksest sisse ning altari ees keerati ringi. Mõne aastaga rüüstati ja lõhuti orel. 1950ndate lõpul lõppes kiriku kasutamine laona, seejärel jäi hoone rüüstatuna ja tühjana seisma. Kirikusse taheti avada muuseum, kuid selle nimel ei tehtud midagi.
Külastasin Pühalepa kiriku esimest korda vist 1976. aasta kevadel klassiekskursiooni käigus. Meiega oli kaasas õpetaja Evald Teras, kellel oli võimalus kirikusse sisse minna. Meeles on tolmune ruum, põrandal vedelev oreliklaviatuur ja tühi orelikapp rõdul. Üks aken oli katki ja seina najale oli pandud palgijupp, mille abil sai ka aknast sisse pugeda.
Kiriku taastamisest hakati uuesti rääkima 1980ndatel, esialgu oli mõte taastada kirik kontserdisaaliks, nagu ka näiteks Niguliste kirik Tallinnas. 1987. aastal (teistel andmetel 1989) oli kirikus tulekahju, milles hävis osa kiriku katusest, suuremat kahju aga õnneks ei sündinud.
Kirik pühitseti uuesti 1993. aastal.
2015. aastal sai Pühalepa kirik uue oreli. Tegemist on annetusega Rootsist Skövde Püha Markuse kirikust, see on suhteliselt väike, kahe manuaalgi ja 18 registriga altariorel. Vana koorioreli taastamine on tulevikuunistus.