Prvním kostelem v Čáslavi byl románský kostel sv. Michala. Kostel byl postaven asi v polovině 12. století. Pánové z Chlumu, zakladatelé tohoto románského kostelíka, vyjádřili tímto aktem svůj nárok na držené území. V kostele je dokonce dosud pochován jeden z příslušníků tohoto rodu, Jistislav. Později se kolem kostela začala rozrůstat osada, a po založení města Čáslavi, což bylo po roce 1248, rozhodla místní obec o vybudování nového většího chrámu. Zhruba v polovině 14. století bylo postaveno nové kostelní trojlodí a současně byla vybudována kaple sv. Anny, dříve kaple Panny Marie Bolestné.

Z vnějšku téměř neviditelný románský kostelík sv. Michala tak splynul s větší stavbou a nyní tvoří zákristii děkanského kostela. Pravděpodobně tehdy došlo k novému vysvěcení kostela, který od té doby nese jména apoštolů Petra a Pavla. Už od počátku bylo v kostele osm oltářů. První vznikly v letech 1358 a 1360, r. 1362 zde byl umístěn oltář sv. Kateřiny, v r. 1387 vznikl samostatný oltář sv. Zikmunda, v r. 1389 oltář sv. Mikuláše, v r. 1390 oltář sv. Leonarda, sv. Felixe a sv. Adaukta. Z r. 1391 pochází zmínka o již dříve existujícím oltáři Panny Marie a v r. 1404 vznikl oltář sv. Kříže. Roku 1405 vznikl oltář sv. Petra a Pavla. Počet oltářů svědčí mimo jiné o dostatku finančních prostředků místních stavů.

Počátkem 15. stol., byla do nároží mezi jižním bokem presbyteria a východní zdí jižní lodi vestavěna věž. Její dostavba začala roku 1491 a skončila roku 1506, kdy byla na věž posazena korouhvička. Po požáru v roce 1452 došlo k některým opravám a úpravám. Na severní straně vznikl přístavek s klenbou o třech polích. Okna na této straně byla zazděna a zakryta střechou přístavku. Další požár v roce 1522 kostel silně poškodil. V roce 1537 proto byly zahájeny rozsáhlé úpravy. Byly nově zbudovány pilíře a klenba stavby, došlo k úpravě přední části západního průčelí s portálem a severozápadní nároží kostela bylo zpevněno mohutným opěrným prvkem. Stavební úpravy probíhaly do r. 1539. Během úprav získal kostel také novou stanovou střechu a bylo zvýšeno vřetenovité schodiště u. V této podobě existuje kostel sv. Petra a Pavla vlastně dodnes, architektonické zásahy provedené v době baroka jsou nepodstatné a řada z nich byla eliminována při rozsáhlé opravě v letech 1908—11. Při třetím požáru v r. 1600 byl zničen krov věže, ale již v roce 1602 měla věž krov nový, s krytinou z mědi. V letech 1618—43 byl kostel několikrát vydrancován.

Další požár o sto tři roky později zničil znovu krov věže. V rámci opravy, dokončené přibližně v roce 1727, byl pořízen nový krov, vybudován byt hlásného a věž osazena hodinami. Během 18. století bylo také vyměněno staré vnitřní zařízení kostela za nové, barokní. Dnešní podoba pochází z přestavby v letech 1910-1911 vedené architektem Kamilem Hilbertem. Při rekonstrukci byly v zazděném výklenku v podvěžní kapli objeveny ostatky snad Jana Žižky z Trocnova.