Kostel v Hraničných Petrovicích najdete v nejvyšším místě obce, ve výšce 590 m n. m., v malém sedle, kterým ve vsi prochází cesta ze Šternberka do Domašova nad Bystřicí. V minulosti byl zároveň na křižovatce cest do Horní Loděnice a Hraničného a Jívové – tyto však již v současnosti nejsou běžně využívány. Zasvěcení kostela sv. Petrovi a Pavlovi souvisí patrně s názvem obce – v obci byly sice už od rané doby slaveny svátky, ale bylo to v den sv. Vavřince (10. srpna) a v den sv. Anny (26. července).
Kostel sv. Petra a Pavla je jednolodní stavba, která je na východní straně zakončena mírně odsazeným pětibokým presbytářem. Na západní straně kostela je čtyřicetimetrová věž na mírně obdélném půdoryse, která je zakončená osmibokou jehlancovou střechou z počátku 20. století. K severní straně presbytáře je připojena přízemní sakristie čtvercového půdorysu. V západním průčelí se nachází jednoduchý portál s kamenným schodištěm (nově vybudovaným v 90. letech 20. století), nad nímž je osazen původní znak majitelů kostela – Liechtenštejnů – s letopočtem „MDCCLXIII“.
V obci existoval kostel zřejmě již před rokem 1500, o čemž svědčí kamenné zbytky původních základů i zpráva z dochovaného inventáře z roku 1672 o zvonu, který byl odlit v roce 1500 a po celou dobu byl v majetku kostela. Starý kostel, pravděpodobně dřevěný, byl roku 1767 pro nebezpečí zřícení uzavřen a následně zbořen. Ještě téhož roku bylo rozhodnuto o stavbě nového kostela. Obec nechala vyhotovit plán a návrh rozpočtu a s žádostí o příspěvek na stavbu nového kostela se obrátila na liechtensteinského knížete Antona Giese von Bärn. Obec i okolní krajina se totiž ještě nevzpamatovala z prusko-rakouských válek a vichřice, která se přes obec prohnala 19. 6. 1764. Dne 25. 7. 1767 obdržela obec rozhodnutí knížete, který byl ochoten nepokrytý zbytek nákladů dodat v materiálové podobě. V roce 1768 byla započata hrubá stavba, která byla dokončena ještě téhož roku. Dohled nad stavbou měl z vrchnostenského úřadu a konsistoře pověřený lokální kaplan August Niemetz z Domašova, který údajně nestavěl podle předloženého plánu, nýbrž podle vlastního vyměření. Celá stavba i s vnitřním vybavením byla dokončena teprve roku 1774, kdy došlo i k vysvěcení nového kostela. V roce 1785 podala obec žádost o převzetí patronátu nad kostelem a roku 1792 byl pozemek kostela prodán do vlastnictví obci.
V roce 1793 věnovala olomoucká panna Barbara Winkler kostelu oltářní obraz, který představuje sv. Petra a Pavla. Je velmi pravděpodobné, že se jedná o dílo Paula Trogera (1698–1762), jednoho z hlavních představitelů rakouského pozdně barokního malířství. Z dobrovolné sbírky byly pořízeny obrazy sv. Anny a sv. Vavřince po stranách presbytáře a v roce 1854 nová kazatelna. V roce 1855 obdržel kostel od Náboženského fondu nový hlavní oltář. Mramorový kříž před vchodem do kostela věnovaly roku 1902 sestry Cäzilia a Viktoria Matznerovy.
Roku 1909 byly ve věži zřízeny hodiny, které vyhotovil hodinář F. X. Beitel z Berouna. Na kostelní věži byl vytvořen výklenek pro ciferníky. Krátce poté došlo k tragické události. 9. června roku 1911 se přes obec přehnala bouře, při které blesk zapálil kříž na střeše kostela, který ihned začal hořet, a v krátké době poškodil velkou část střechy a věže. Nakonec spadla věž s hodinami a zvony, které se roztavily (střední a menší zvon) a největší zvon z roku 1500 se roztříštil. Všechny střešní podlahy shořely. V ranních hodinách jako obvykle sloužil mši farář Franz Klimek mezi dohořívajícími ruinami. Ihned, aby nespadla klenba lodi, se započalo s rekonstrukcí. Stavební práce prováděl zednický mistr Mahner z Města Libavé, natěračské a podobné práce mistr Kern ze Staré Vody. V krátké době stála loď kostela se střechou v rekonstruovaném stavu. Bylo rozhodnuto, že místo malé věže bude vystavěna vyšší – pro ciferník s hodinami. Díky milodarům a snahám faráře Klimka byl kostel opět velmi brzy v dobrém stavu i s vnitřní výzdobou. Věžní hodiny opět zhotovil hodinář F. X. Beitel, zvony Fa. Ad. Hillers Wtw. z Brna a malby kostelní malíř Herodeck z Nového Města na Moravě. Varhany vytvořil petrovický varhanní stavitel Josef Mader. (Josef Mader se narodil 7. 4. 1857 v Hraničných Petrovicích. Varhanářská dílna a malá slévárna na výrobu zinkových píšťal byla v domě č. p. 17 –dnešním kulturním domě. První varhany postavil v roce 1888 v Jívové, další v Horní Loděnici, Melči, Kluboukách u Brna, Slezské Hartě, Jindřichově u Bruntálu a Huzové. V roce 1896 opravoval varhany v chrámu sv. Mořice v Olomouci. Petrovické varhany z roku 1911 jsou posledním známým nástrojem, který Mader postavil.) Po dokončení oprav byl kostel slavnostně vysvěcen.
Po válce kostel spíše chátral. Přesto z přelomu 50. a 60. let 20. století pochází dvě vitrážová okna za oltářem – na okně vpravo je vyobrazen svatý Václav se štítem s černou orlicí ve znaku; vlevo je svatá Ludmila. V letech 1991–1992, díky velkému nasazení místního faráře P. Antonína Pospíšila, byl kostel kompletně opraven, včetně dvou nových zvonů. Celou opravu financovali z vlastních úspor sudetští Němci, kteří zde původně žili a ke kostelu měli osobní vztah. Díky jejich zájmu a finančnímu přispění bylo možno opravit kostel a zachovat tak tuto nejvýznamnější stavbu v obci pro další generace.
V roce 1993 byly firmou z Valašského Meziříčí opravovány varhany. V průběhu této opravy nedošlo k výraznějšímu zásahu do mechaniky anebo dispozic nástroje, nejvýraznější změnou se stala barva varhanní skříně. Do té doby zelenou (a původně pravděpodobně hnědou) skříň nahradila bílá s několika zelenými, zlatými a červenými detaily. Varhanní skříň je rozdělená do pěti píšťalových polí, nejvyšší centrální věž je ukončena novobarokní řezbou. Výzdoba varhanní skříně nese historizující ornamenty 19. století.
Pro nedostatek zájmu o duchovní život byla po 150 letech zrušena farnost Hraničné Petrovice a od roku 2008 je filiálním kostelem farnosti Jívová, která je pod duchovní správou šternberské farnosti. Mše svaté se v kostele konají nepravidelně.