Pierwsza wzmianka o parafii w Nowym Żmigrodzie pochodzi z 1325 r. Przed 11 maja 1511 r. biskup krakowski Jan Konarski podniósł parafię do godności prepozytury i erygował przy kościele parafialnym kolegium mansjonarzy. Ok. 1595 r. ordynariusz diecezji krakowskiej kard. Jerzy Radziwiłł utworzył dekanat żmigrodzki. Według akt wizytacyjnych, na pocz. XVII w. naprzeciwko bramy miejskiej znajdował się budynek szpitala prepozyturalnego z własną kaplicą. W 1603 r. właściciel miasta Andrzej Stadnicki refundował klasztor Ojców Dominikanów. Konwent funkcjonował do II poł. XVIII w., kiedy to został zlikwidowany przez zaborcze władze austriackie. W Nowym Żmigrodzie istniała również szkoła parafialna wzmiankowana po raz pierwszy w 1527 r.
Kościół parafialny został wzniesiony w stylu gotyckim. Akta wizytacyjne diecezji krakowskiej z XVII w. określają go mianem murowanego. Według nich nosił on wezwanie Świętych Piotra i Pawła. Świątynia posiadała wówczas pięć ołtarzy. Wchodziła w skład kompleksu obronnego zamku żmigrodzkiego.
Została zbudowana na rzucie poziomym gotyckim ze szkarpami.
Świątynia była wielokrotnie niszczona. Po raz pierwszy ucierpiała prawdopodobnie podczas oblężenia i szturmu miasta przez wojska węgierskie w 1474 r. Wtedy to, według bp. Marcina Kromera, Madziarzy ostrzelali zamek z bombard. W 1522 r. i 1577 r. kościół spłonął podczas wielkich pożarów miasta. Po pożarze w 1694 r. pozostały tylko same mury świątyni. 17 kwietnia 1843 r. spalił się kościół wraz z połową miasta. Wielokrotnie płonęła również dzwonnica (1846, 1882). Od I poł. XVII w. rozpoczął się upadek społeczny i gospodarczy miasta. Dlatego na odbudowę świątyni przeznaczano bardzo skromne środki, a prawdopodobnie gotyckie sklepienia zastąpiono drewnianym stropem. Odbudowany po pożarach kościół konsekrował 28 czerwca 1857 r. biskup przemyski obrządku łacińskiego Franciszek Wierzchlejski. Znaczna część wyposażenia wnętrza została przejęta ze zniesionego kościoła i klasztoru Ojców Dominikanów. W czasie II wojny światowej kościół został uszkodzony i zdewastowany podczas walk niemiecko-sowieckich na przełomie 1944 i 1945 r. Dzieła jego odnowy dokonał bł. ks. Władysław Findysz.
Już na pocz. XX w. powstała koncepcja budowy nowego kościoła ze względu na niewystarczające rozmiary obecnego oraz, jak sądzono, brak wartości artystycznych. Dlatego ówczesny wicedziekan żmigrodzki i parafianie podjęli inicjatywę budowy nowego kościoła po stronie południowej miasta. Wybuch I wojny światowej zniweczył jednak te plany, a zachowana świątynia jest jedną z nielicznych gotyckich budowli na terenie naszej diecezji. Jest ponadto niemym świadkiem kapłańskiej posługi bł. ks. Władysława Findysza i miejscem jego szczególnego kultu.