
Barokizovaný, pův. pozdně gotický kostel má obdélnou loď, podepřenou opěráky, s pětiboce uzavřeným presbytářem. Mezi opěráky východního pole závěru je přístavba kostelní pokladnice s půdorysem trojlistu. K jižní straně kněžiště přiléhá kaple sv. Otýlie čtvercového půdorysu, k severní straně patrová sakristie.
Západní průčelí s hranolovou věží v ose je zakryto postranními čtvercovými kaplemi. Před věží je představěná předsíň s terasou.
Hlavní oltář je prací Jeronýma Forstera, který pracoval v dílně O. Schweigla, hlavní oltářní obraz vytvořil malíř Anton Weidlich (1784). Sochařskou výzdobu vytvořil Ondřej Schweigl. Interiéry kostela jsou zdobí křížová cesta ak. malíře Joži Úprky, malby prof. Hellera a další hodnotný mobiliář.
Varhany z let 1797 - 1802 od Ambrosia Ronsonyho byly v 30. letech 19. stol. ozdobeny a zprovozněny brněnským varhanářem Františkem Habigerem.
Starší kostel, který stával na jiném místě, byl vypálen za husitských válek r. 1423 společně s městem. Nový kostel nechal postavit biskup Tas z Boskovic a Černé Hory. Se stavbou trojlodní haly bez věže u městských hradeb se započalo roku 1464. Nový kostel však krátce po dostavbě vypálil vévoda Jiří z Münsterberka, protože biskup Tas nepodporoval krále Jiřího z Poděbrad. Biskup zemřel roku 1482 na mor a spálený kostel byl dostavěn a vysvěcen až roku 1496 nikopolským biskupem Ondřejem. Od roku 1607 se zmiňuje samostatná "německá" kaple, zasvěcená snad Sedmibolestné Panně Marii, s kůrem, kazatelnou a malovaným krucifixem (V 1. pol. 18. stol. nahrazena novou kaplí Sedmibolestné Panny Marie; r. 1900 pro špatný stav stržena a postaveny dvě nové kaple). Další pohromou pro město bylo dobytí Vyškova Švédy roku 1643. Ti kostel vydrancovali a zničili i nové varhany. Zmocnili se i ukrytých cenností a peněz na dostavbu kostela, které tehdy pod oltář sv. Kříže ukryl děkan Adam Tubernátor. Do roku 1653 stála při kostele kostnice. V 60. letech 17. století byla k závěru kostela přistavěna klenutá pokladnice. Zpráva z roku 1665 se zmiňuje o špatném stavu kostela - střecha byla děravá, zatékalo do krovu a na klenbu, která hrozila zřícením. Střecha byla opravena zřejmě roku 1672 (žádost městské rady biskupovi o materiál). V letech 1689-1690 byla k jižní straně presbytáře přistavěna kaple sv. Otýlie, kterou nechal postavit na své náklady děkan Jan Kašpar Hauser, olomoucký a vratislavský kanovník (r. 1690 zde byl pohřben). Architekt kaple není známý. Roku 1692 nechal kapli biskup Karel z Liechtenštejna vyzdobit štukami od italského barokního sochaře a štukatéra Baltazara Fontany a malbami (výjevy ze života světice) od malíře Jonase Drentwetta. Roku 1705 odkázal kostelu probošt Václav Alexander Neupauer majetek na stavbu věže, která měla nahradit samostatně stojící zvonici. Věž byla přistavěna v letech 1729-1735, také byla v l. 1729-1732 přistavěna nová kaple Sedmibolestné Panny Marie po jižní straně věže, která nahradila původní kapli (zmiňovanou na počátku 17. stol.). Kaple byla opět označovaná jako "německá", neboť byla navštěvována do pol. 19. stol. německým obyvatelstvem z přifařených Rostěnic u Vyškova. Kapli nechal postavit děkan Hnátek, za přispění neznámého dobrodince. Architekt kaple je také neznámý. Do období mezi lety 1690 – 1735 datují V. Richter a Z. Kudělka opravu kostela podle neznámého plánu arch. Givanna Pietra Tencally. Tato oprava patrně proběhla po roce 1728, neboť do roku 1728 spadá naléhavá žádost děkana Václava Hnátka biskupovi o opravu kostela, který byl v té době v dezolátním stavu. Roku 1753 při velkém požáru města shořela střecha kostela a byl zničen presbytář i kaple sv. Otýlie. Silně poškozená kaple byla při následující opravě zrušena a sloužila nadále jako depozitář. Samotný kostel zůstal celých dvacet let bez střechy - na vině byla morová epidemie, která město téměř vylidnila. R. 1760 byl kostel vybaven kryptou. Roku 1773 se zřítil jeden ze šesti pilířů klenby lodi. Demolicí narušených částí kostela byl téhož roku pověřen stavitel a architekt František Antonín Grimm. Následnou kompletní barokizaci provedl v letech 1773-1789 Jan Antonín Křzaupal von Grünenberg, který byl pověřen opravou kostela. V letech 1816-1819 byl kostel znovu opravován, roku 1820 byla opravena kazatelna a křtitelnice. Roku 1843 byla stržena zchátralá kupole kaple sv. Otýlie (poničena požárem) a kaple byla r. 1844 nově zastřešena. R. 1881 byla po řadě oprav snesena narušená báň věže a byla prozatímně nahrazena nízkou jehlancovou střechou. V letech 1901-1903 byla celkově opravena věž (zastřešena bání) a západní průčelí kostela. Kaple Sedmibolestné Panny Marie, která byla ve velice špatném stavu, byla v l. 1900-1901 nahrazena dvěma novými kaplemi, také byla přistavěna předsíň s terasou (neobarokní projekt architekta Richarda Völkla z Kolína nad Rýnem). Šestice zvonů i s měděnou krytinou střechy byla zrekvírována za 1. světové války. Zůstal jen zvon Maria z roku 1549. R. 1929 byl pořízen nový zvon sv. Václava..