Pedersören kirkko on yksi pohjanmaan vanhimmista keskiaikaisista kirkoista. Pääsisäänkäynnin yläpuolella oleva vuosiluku 1250 on peräisin melko vanhasta ja epävarmasta historiankirjoituksesta. Siinä mainitaan, että Pedersören ensimmäinen kirkko rakennettiin noin vuonna 1250. Pedersören seurakunta mainitaan useita kertoja 1300-luvun alkupuolella, kun taas Pedersöre pitäjänimenä varmoissa lähteissä mainitaan vuonna 1348.

Ensimmäinen kirkko oli luultavasti pieni kivi tai puukappeli. Nykyisen kirkon vanhimmat osat ovat peräisin keskiaikaisesta kirkosta, joka luultavasti rakennettiin 1400-luvulla. Suorakaiteen muotoisen kirkon alttari on itään päin ja torni länteen päin.  

Ristikirkon uudelleenrakennus aloitettiin vuonna 1787. Vaikea tehtävä uskottiin 33-vuotiaalle Jakob Riijfille. Kustaa III:n hyväksymä piirustuksia ei onneksi noudatettu täydellisesti. Siten kaunis 65 metriä korkea torninhuippu pelastettiin jälkipolville. Se kuitenkin tuhoutui tulipalossa heinäkuussa 1985 yhdessä kirkon alttaritaulun ja urkujen kanssa. 

Palon jälkeen täysin uudistettu kirkko otettiin udelleen käyttöön adventtina 1986. Täysin mekaanisissa uruissa on 39-äänikertaa ja ne ovat peräisin vuodelta 1988. Nämä kirkon viidennet urut ovat tanskalaisen Marcussen & Son valmistamat. 

1400-luvulta peräisin oleva puinen Madonna-patsas on osa alttarikaappia. Skrufin suvun lahjoittama 14-osainen kynttilänjalka on peräisin vuodelta 1867.