První písemně doložená zmínka o farním kostele sv. Matouše v Postřelmově pochází z r. 1409, ale kostel byl pravděpodobně postaven již ve 14. století zemany ze sousedních Závořic a Kolšova, kteří zde pohřbívali své zesnulé příslušníky rodu s manželkami. Šlo o gotickou stavbu, k lodi byla přistavěna ze severní strany věž opatřená již tehdy vchodem do chrámu. Loď kostela byla vystavěna z lomového kamene a zřejmě zvenku i uvnitř byla omítnuta.

Roku 1664 nebo 1665 kostel velmi poničil požár. Rekonstrukce proběhly v tehdy moderním barokním slohu, který nahrazoval gotiku. Loď i kněžiště byly barokně zaklenuty, ve zdech byla prolomena nová okna. V r. 1853 byla nutná další oprava značně zchátralého kostela. Tehdejší farář Melchior Feigerle  navrhoval starý chrám strhnout a místo něho na stejném místě nebo za farskou stodolou postavit nový, který měl být kratší, avšak mnohem širší, s kaplemi po stranách a s věží obrácenou k silnici. Představitelé obce s ohledem na nákladnost stavby nového kostela prosadili opravu a rozšíření stávajícího chrámu. Bylo zbořeno zaklenuté kněžiště i sakristie a kostel byl vystavěn do dnešní podoby. Loď kostela byla prodloužena směrem k silnici a zakončena novým kněžištěm. Při přestavbě kostela byl zrušen horní kůr a ponechán jen dolní, který byl prodloužen.

Současné vybavení kostela pochází z 19. a 20. století. Za pozornost stojí hlavní oltářní obraz evangelisty sv. Matouše namalovaný barokním mistrem Ignácem Raabem patrně roku 1780.  Zmínka o tomto obrazu je uvedena r. 1806 v naši farní kronice), sousoší Bořivojův křest z roku 1894 od sochaře Josefa Strachovského i nástropní malba zobrazující Poslední večeři. Jistě vás zaujme i ornamentální řezbářská výzdoba čel lavic a zvláště pak řezbářská práce na obou zpovědnicích, které byly do chrámu instalovány v r. 1894. Chloubou kostela jsou varhany postavené v r. 1889 novojičínskou varhanářskou firmou v čele s varhanářem Karlem Neusserem. Současné tři zvony z dílny paní Laetitie Dytrychové z Brodku u Přerova byly na věž kostela umístěny v r. 1969.