Historie kostela
Kostel byl považován za nejstarší v Prostějově na základě svého starobylého titulu a na základě domněnky, že v jeho okolí stávala původní ves Prostějovice, ze které se koncem 14. století stalo město Prostějov. Archeologický průzkum však nezjistil v blízkosti kostela stopy po osídlení z té doby. První písemná zmínka o kostele sv. Petra a Pavla je z roku 1475 v Nejstarší městské knize prostějovské. Jaká byla původní podoba kostela, jehož založení odhadujeme na 12. až 13. století nevíme. U kostela byl nejstarší prostějovský hřbitov. Až do roku 1763 se pohřbívalo také v kostele. Význam kostela klesl koncem 14. století po založení augustiniánského kláštera s kostelem. V 15. století kostel vyhořel. Po dokončení obnovy kostela sv. Kříže byla samostatná farnost u sv. Petra a Pavla v roce 1588 zrušena a kostel se stal filiálním. Dle záznamu ve Wolného Moravské církevní topografii z roku 1857 víme, že kostel měl rozměry 22,5 x 7,5 m. Jeho výška byla 9,4 m. Byl zděný. Měl nízkou věž se třemi zvony. Kostel měl sedm oken, čtyři v lodi a tři v presbytáři. Strop byl dřevěný, rovný a malovaný. Také kůr byl dřevěný. Kněžiště bylo klenuté. Kromě hlavního oltáře byly v lodi ještě dva boční oltáře. Bylo v něm také několik náhrobků a na zdech byly nápisy. V kostele bylo rozvěšeno 15 obrazů.
V letech 1728 až 1730 byl původní kostelík celkově přestavěn a rozšířen. Pod kostelem byla při přestavbě vybudována krypta. Přestavěný kostel měl novou vysokou věž. Hlavní oltář byl dřevěný a v roce 1731 na něj bylo umístěno vzácné sousoší Poslední večeře Páně. Za oltářem byl obraz Panny Marie svatotomášské. Později byl nahrazen oltářním obrazem sv. Petra v okovech. Došlo tak k nesouhlasu zasvěcení kostela s hlavním oltářem. Teprve v roce 1736 byl první boční oltář na evangelní straně lodi zasvěcen patronům kostela sv. Petru a Pavlu. Kostel byl po přestavbě benedikován prostějovským děkanem Janem Birhelem dne 29. 6. 1731. Svědčí o tom letočetný nápis nad hlavním vchodem do kostela.
V roce 1740 byla věž kostela stržena silnou vichřicí. Místo ní byla postavena jen věžička ve tvaru nízkého čtyřbokého jehlanu, která byla na kostele dvě stě let. Až v roce 1940, při celkové opravě kostela, byla tato věžička nahrazena současnou zvýšenou věží s kopulí (dle návrhu brněnského architekta Klaudia Madlmayra).
Starý prostějovský hřbitov, který se rozkládal kolem kostela byl obehnán zdí. Byl několikrát rozšířen a v roce 1726 byla u severozápadní strany kostela vybudována hřbitovní kaple sv. Lazara. Jde o volně stojící stavbu, šestiúhelníkového půdorysu v raně barokním slohu. Na starém hřbitově se pohřbívalo až do roku 1900, kdy byl otevřen nový hřbitov na Brněnské ulici.
V roce 1941 byl dřevěný hlavní oltář nahrazen novým mramorovým oltářem dle návrhu K. Madlmayra, který dne 29. 6. 1941 posvětil Dr. Oldřich Karlík, generální vikář Arcibiskupství olomouckého.
Na věži kostela je nejstarší zvon v Prostějově z roku 1506. Váží 300 kg. Je zasvěcen sv. Petru a Pavlu. Na věži byly celkem čtyři zvony, tři z nich však byly zrekvírovány za 1. a 2. světové války.
Od roku 1934 působila při tomto kostele Společnost Božského Spasitele – salvatoriáni. Ti dosáhli obnovení samostatné farnosti v roce 1938. Jejich působení bylo násilně přerušeno za 2. světové války nacisty (v roce 1942 byl v kounicových kolejích v Brně popraven salvatorián P. ThDr. Metoděj Mičola) a za komunistického režimu, kdy jejich správu přerušila násilná likvidace řádů v roce 1950. Samostatná farnost a salvatoriánská správa byla obnovena v roce 1990, kdy byla vyfařena z farnosti Povýšení sv.Kříže. Salvatoriáni mají v Prostějově svůj provincialát.
Od léta roku 2015 byl rok farářem prostějovský děkan P. ICLic. Mgr. Aleš Vrzala než došlo k výměně obsazení s druhou prostějovskou farností Povýšení svatého Kříže a od léta 2016 působí ve farnosti Salesiáni Dona Boska.
