Farní chrám sv. Matouše byl pravděpodobné postaven již ve 14. století. První zmínka o něm je z roku kdy byli jeho ochránci (patrony) zemané z Kolšova z rodu Závořických, jejichž ostatky jsou pravděpodobně v kostele pohřbeny. V roce 1447 přešly majetky kolšovských vladyků v Postřelmově i s patronátním právem ke kostelu do vlastnictví majitelů jiné části obce, kterými byli zemané ze Zvole. Po roce 1500 patřila ves s kostelem Žerotínům a Boskovicům. Tehdy byl od druhé poloviny 16. století do třicetileté války při chrámu evangelický kněz. V roce 1592 byla na hřbitově, který obklopoval kostel, postavena vedle bývalé brány pozdně renesanční hrobka vladycké rodiny Bukůvků z Bukůvky sídlících v nedaleké Chromči, vsi patřící do farního obvodu postřelmovského. Tehdy již k postřelmovské farnosti nepatřila ves Závořice (zanikla při stavbě rybníka v 80. letech 15. stol.), avšak od 90. let 15. století bylo k chrámu sv. Matouše náhradou přifařeno Rovensko, které vedle Leštiny a Chromče tvořilo po dvě století postřelmovský farní obvod.
První zobrazení kostela pochází z roku 1623 a je zachyceno na Aretinově mapě zábřežského panství, kterou nechal vyhotovit nový majitel konfiskovaného panství Karel Karel z Lichtenštejna. Rod Lichtenštejnů vlastnil Postřelmov i s patronátním právem ke kostelu až do roku 1848. Na Aretinově mapě vidíme gotickou podobu chrámu sv. Matouše, k lodi kostela je přistavěna ze severní strany věž opatřená již tehdy vchodem do chrámu. Krovy věže vytvářejí špici se čtyřmi věžičkami v rozích, nižší kněžiště uzavírá na východní straně chrámový prostor.
Kostel v této podobě roku 1664, nebo na počátku roku 1665 vyhořel. Při obnově svatyně byla loď zaklenuta (současná tři klenebná pole v západní části lodi), původní užší kněžiště bylo prodlouženo, což si pravděpodobné vyžádalo jeho zaklenutí. Západní průčelí kostela bylo opatřeno předsíni, v jejíž severní straně byl vybudován vstup ze hřbitova na spodní chór kostela. V této podobě se nám předsíň dochovala dodnes.
Věž byla poněkud zvýšena a zakončena cibuli s lucernou, na špici věže byla umístěna pozlacená makovice, dále korouhvička a hvězda. Střecha chrámu byla kryta šindelem a opatřena malou věžičkou, sanktusníkem, který i před požárem zdobil střechu kostela. Mezi léty 1665 a 1806 byla ke kněžišti přistavěna sakristie.
Roku 1806 měl kostel vedle hlavního oltáře s obrazem sv. Matouše další dva oltáře postranní, jeden s obrazem Tovaryšstva Ježíšova a protější s obrazem sv. Barbory. Soška sv. Michala byla umístěna před hlavním oltářem a po jeho stranách stály dřevěné sochy sv. Jana Evangelisty a sv. Jana Křtitele. Chrám byl opatřen dvěma chóry; dolní sloužil při bohoslužbách věřícím, na horním chóru, kde byly varhany s 10 mutacemi, hrávali hudebníci.
V roce 1853 byl kostel rozšířen. Kněžiště i sakristie byly zbořeny a loď byla prodloužena směrem k silnici a zakončena stejně Širokým i vysokým kněžištěm. Klenebná pole z roku 1853 (od širokého pasu s obrazem Poslední večeře Páně ke kněžišti) tvarově respektují klenutí z roku 1665 a přispívají ke sjednocení chrámového prostoru. Nový kostel je od té doby více než 35 m dlouhý. Při přestavbě roku 1853 byl také zrušen horní chór a ponechán jen dolní, který byl prodloužen. Chrám dostal novou sakristii, nad níž bylo zřízeno oratorium. Celá stavba byla zakryta novou, břidlicí krytou střechou. Velká věž i malý sanktusník byly pokryty plechem, opatřeny bání a na vrchol velké věže byl umístěn pozlacený kříž.
V té době tvořily farní obvod vedle Postřelmova vesnice Sudkov (od r. 1717), Chromeč a Leština (do r. 1855). Rovensko se roku 1753 vrátilo k zábřežské farnosti.
Současné vybavení kostela pochází z 19. a 20. století. Oltářní obraz sv. Matouše byl při restaurováni v roce 1968 přisouzen neznámému autorovi vídeňské školy, pravděpodobně z let 1860 – 1870. Za pozornost stojí ornamentální řezbářská výzdoba čel lavic a zvláště pak řezbářská práce na obou zpovědnicích, které byty do chrámu instalovány v roce 1894. Chloubou kostela jsou varhany postavené firmou K. Neuser z Nového Jičína v roce 1889 a financované převážné z odkazu rolníka Viléma Pelcla. Do nového nástroje byly použity z původních varhan některé dřevěné píšťaly na basový rejstřík. Varhany mají deset samostatně znějících rejstříků ve dvou manuálech a pedálu, spony a později zabudované tremolo. Slouží již přes sto let při bohoslužbách a v poslední době i při koncertech.
Každou neděli zvou na mši tři kostelní zvony, největší z nich zasvěcený sv. Matouši, prostřední Panně Marii a nejmenší umíráček, které pospolu vyzvání na věži od roku 1969. Staré zvony padly za oběť válkám, včetně obou válek světových. Věřme, že současné zvony z dílny Marie Tomáškové-Dytrychové z Brodku u Přerova budou zvonit v míru mnoha dalším generacím.