Kostel v Podivíně stával již v 11. století. Kostel v románském slohu, byl původně dřevěný. Ve 14. století byl pak přestavěn do slohu gotického. Dá se předpokládat, že původní kostel stával na jiném místě, než stojí dnešní kostel, jelikož se zbytky původní stavby našly mnohem níže.

Počátky stavby dnešního kostela sv. Petra a Pavla v Podivíně sahají do 1. pol. 13. století. Jde o jednolodní stavbu s polygonálním závěrem kněžiště. Kostel má s přistavěnými dvěma kaplemi, kaple sv. Anny a kaple sv. Jana Nepomuckého, tvar kříže. Má dva vchody, tři oltáře a celkem je chudě vyzdoben. 

Kostelní věž, jež vyniká především výškou, je zakončena na každém rohu věžičkou a uprostřed vížkou. Ve věži se nacházejí tři zvony ze zvonoviny (Petr a Pavel, Cyril a Metoděj, Karel a Pankrác), které sem byly instalovány roku 2011 a jeden menší zvon ze železa, kterému se říká umíráček. Zvony ze zvonoviny se do kostelní věže vrátily po dlouhé době, jelikož původní zvony byly kostelu odebrány v první světové válce a byly nahrazeny železnými.