Die katholische Gemeinde in der Region Tula existiert seit dem 19. Jahrhundert. In den 1840er Jahren kümmerte sich der Kaplan der Moskauer Eisenbahn um die katholischen Gläubigen in Tula. Nach der Niederschlagung des Aufstands von 1863 kamen viele Katholiken aus Polen, Litauen und Weißrussland nach Tula. W. I. Smidovich, Mitglied des Kirchenrates der katholischen Gemeinde Tula, war ein bekannter Arzt, Gründer des Tula Stadtkrankenhauses und der Sanitätskommission sowie einer der Gründer der Gesellschaft der Tula Ärzte. Sein Sohn, W. W. Veresajev, wurde ebenfalls Arzt und Schriftsteller. 1885 eröffneten die Katholiken von Tula eine Kapelle in einem privaten Haus, doch sie war zu klein, und die Gemeinde bat um Land für den Bau einer Kirche. Am 28. Mai 1893 genehmigten die Behörden den Bau einer Kirche am Stadtrand von Tula an der Kiewer Straße.

Der Grundstein der Kirche wurde am 15. Mai 1894 an der Kreuzung des heutigen Lenin-Prospekts und der L. Tolstoi-Straße gelegt. Der Bau wurde von dem Provinzarchitekten Evarist Skavronsky geleitet. Die Kirche wurde 1896 vom Generalvikar der Mogiljower Metropolie, Franziskus Symon, geweiht. Ab 1898 arbeitete ein ständiger Priester in der Gemeinde, das Gemeindeleben nahm zu, eine Bibliothek wurde eröffnet und zu Feiertagen wurden Aufführungen veranstaltet. Laut der Volkszählung von 1897 lebten in der Tula Provinz 1224 Katholiken, die meisten von ihnen in Tula.

Nach 1917 sank die Zahl der Gemeindemitglieder drastisch aufgrund der Emigration von Polen und Balten nach dem Machtantritt der Bolschewiki. 1918 wurde das Eigentum der Kirche zum Volkseigentum, aber die Kirche blieb aktiv. 1926 wurde der Pfarrer J. Pawlowitsch verhaftet, und 1932 wurde die Kirche geschlossen. Später befanden sich in dem Gebäude die Redaktion der Zeitung „Junger Kommunar“ und ein kriminaltechnisches Labor.

1993 wurde die katholische Gemeinde Tulas wiederbelebt, aber die Kirche blieb im Besitz einer anderen Organisation. 1995 erhielt die Gemeinde eine Garage für die Durchführung von Messen. Bis zum 30. März 2004, als die Kirche offiziell der Gemeinde übergeben wurde, fanden die Messen in der Garage statt.

Die Rückgabe der Kirche wurde durch die Appelle des Apostolischen Nuntius in Russland, Antonio Mennini, und die Unterstützung des Erzbischofs von Tula und Belew Alexius, der gegen die Übergabe der Kirche nichts einzuwenden hatte, möglich. Nach Erhalt der Genehmigungen begann 2006 die Restaurierung der Kirche, die 2007 abgeschlossen wurde.

Am 23. Dezember 2007 wurde die Kirche feierlich eröffnet. Am 6. Juli 2008 weihte der Erzbischof und Metropolit Paolo Pezzi die restaurierte Kirche, in den Altar wurden die Reliquien des heiligen Johannes Bosco, der seligen Celina Bożencka und der heiligen Elisabeth eingelegt. Am 17. Juni 2012 wurde der Kirche eine neue digitale Orgel der italienischen Firma „Viscount“ übergeben, und am 30. September fand das erste Orgelkonzert in Tula statt.

Die Kirche der Heiligen Apostel Peter und Paul wurde im neugotischen Stil aus rotem Ziegelstein erbaut. Das Projekt wurde von dem Provinzarchitekten Evarist Skavronsky entworfen. Über dem Haupteingang erhebt sich ein Turm mit zwei seitlichen Türmen. Früher standen am Eingang Statuen der Apostel Peter und Paul, die in der Sowjetzeit verloren gingen. In der Nische des Turms befand sich eine Statue der Jungfrau Maria, die ebenfalls verloren ging. Fotos des ursprünglichen Innenraums sind nicht erhalten geblieben, und bei der Rekonstruktion in den Jahren 2006-2007 wurde das Innere der Kirche in einem modernen Stil gestaltet, der sich von der Neugotik unterscheidet.