Nach einer bewegten Vorgeschichte wurde am 10. August 1862, dem Gedenktag des mittelalterlichen Stadtpatrons St. Laurentius, in Winterthur erstmals seit der Reformation wieder ein offizieller katholischer Gottesdienst gefeiert, und zwar im Betsaal der alten Stadtkanzlei. Am 13. Dezember 1863 fand die Gründungsversammlung der katholischen Kirchgemeinde von Winterthur statt.
Da der Stadtrat den Wunsch hatte, dem neu entstehenden Quartier hinter dem Bahnhof einen angemessenen Mittelpunkt zu geben, unterstützte er den Bau der katholischen Kirche durch die Abgabe einer zentral gelegenen grossen Landparzelle. So wurde im Sommer 1862 eine beachtliche Fläche im Quartier Neuwiesen ausgeschieden und im Frühjahr 1864 an die katholische Kirchengemeinde überschrieben. Dadurch erhielten die katholischen Gläubigen einen repräsentativen Standort für den Bau ihrer ersten Winterthurer Kirche. Als einziges öffentliches Gebäude im neuen Quartier nahm die Kirche eine Vorrangstellung ein, welche durch die darum liegende Platzanlage noch unterstrichen wurde.
Für die Planung wurde 1864/1865 ein Wettbewerb veranstaltet, aus dem das Projekt des Winterthurer Stadtbaumeisters Wilhelm Friedrich Carl Bareiss siegreich hervorging. Die Bauarbeiten setzten im Sommer 1866 ein, ein Jahr später wurde die Kuppel vollendet. 1867 wurden von der Kirchgemeindeversammlung die Heiligen Petrus und Paulus als Kirchenpatrone bestimmt, dies als Ausdruck der Verbundenheit mit dem Papst und der römischen Kirche in Zeiten des Kulturkampfs. 1868 konnte die Kirche St. Peter und Paul im Rohbau fertiggestellt werden; der weitere Ausbau verzögerte sich aus Kostengründen. Am 5. Juli 1868 eröffnete Dekan Rüttimann die Kirche im Beisein von Vertretern der kantonalen Regierung samt Staatsschreiber und Dichter Gottfried Keller sowie des Stadtrats von Winterthur.
Der Innenausbau der Kirche musste aus Kostengründen zunächst hinausgeschoben werden. Deshalb war das Schiff 1868 bloss mit einer Flachdecke überspannt, und einfache Tischaltäre sowie eine schlichte Kanzel dienten als Notausstattung. Bis 1887 besass die Kirche auch kein richtiges Geläut, sondern nur eine einzelne kleine Glocke. 1883 wurde dann der Innenausbau an die Hand genommen und innerhalb von zehn Jahren zu Ende geführt. Die Kirche wurde eingewölbt und eine Empore mit Orgel eingebaut, aufwendige Altäre wurden aufgestellt, farbenprächtige Glasfenster eingesetzt, und die Kirche erhielt eine passende Ausmalung. Dies geschah nach Plänen von Heinrich Viktor von Segesser von Brunegg. August F. Martin übernahm die weitere Ausarbeitung und einen Teil der Ausführung. Pater Albert Kuhn aus dem Kloster Einsiedeln erstellte das ikonografische Programm und überprüfte die Altarentwürfe. Diese wurden von Josef Eberle realisiert. Josef Traub führte die Dekorationsmalerei aus, während die figürlichen Wandbilder an den Langhauswänden von einem Sohn des verantwortlichen Malers, Alfons Martin, stammen.
Um ein angemessenes Geläut anschaffen zu können, gründete man 1884 einen Glockenverein. Im März 1887 waren 15'000 Franken beisammen, sodass bei der Glockengiesserei Jakob Keller in Zürich vier Glocken in Auftrag gegeben werden konnten. Am 10. Juli 1897 weihte Bischof Johannes Fidelis Battaglia die fertig ausgestattete Kirche ein.
1925 wurde das Gotteshaus durch den Anbau einer Sakristei nach Plänen von Hermann Zangerl erweitert, dies in Form eines Chorumgangs. Gleichzeitig renovierte man das Äussere der Kirche. Zwischen 1939 und 1946 erfolgte eine umfassende Sanierung des Innenraums, wobei der Dachstuhl und die Fundamente statisch verstärkt wurden. Da das Kirchenschiff auch isoliert wurde, gingen die bisherigen Malereien weitgehend verloren. Für den Bilderzyklus zum Leben der Kirchenpatrone schuf August Frey einen Ersatz. Die Dekorationsmalerei wurde dem Zeitgeschmack entsprechend aufgehellt und die Kirche weiss gestrichen. Die ursprünglichen, reich ornamentierten Glasfenster der Kirche wurden im Chor durch einfachere Buntglasfenster, im Schiff durch helle Fensterscheiben mit einzelnen Heiligenbildern ersetzt. Von der originalen Bemalung blieb schliesslich nur die neogotische Gewölbemalerei erhalten.
1982–1984 wurde die Kirche unter der Leitung der kantonalen Denkmalpflege einer Gesamtrenovierung unterzogen. Das Ziel war es, die neogotische Kirche in wesentlichen Teilen in ihre ursprüngliche Gestalt zurückzuführen, was anhand von Fotografien und Farbbefunden möglich war. Nach den Vorgaben der Liturgiekonstitution des II. Vatikanums (Versammlung der römisch-katholischen Weltkirche, 1962–1965) schuf man hierbei auch einen freistehenden Volksaltar sowie einen Ambo, welche sich in die zurückgeführte Ausgestaltung der Kirche harmonisch einfügen. Damals wurde auch die Orgel durch ein Instrument der Firma Späth mit 36 Registern ersetzt. Die Stadt würdigte die sorgfältige Arbeit 1984 mit der Verleihung des Emch-Preises.
