In den 1920er Jahren realisierte die Stadt diverse Bauprojekte geradezu in Rekordzeit. So beschloss der Magistrat am 3. Dezember 1924 den Neubau der Steintorbrücke. Baubeginn war vor nunmehr 100 Jahren im Mai und am 1. November 1925 hielt der Oberbürgermeister Walther Ausländer bereits die Festrede zur Einweihung der massiven und architektonisch schönen Brücke. „Möge der Verkehr, der sich von dieser Stunde ab über die neue Brücke an dieser alten Straße entwickeln wird, wie ein befruchtender Strom dem Wirtschafts- und Verkehrsleben unserer Stadt zum Segen gereichen!“, wünschte sich damals das Stadtoberhaupt.

Zumindest bis zur Eröffnung des Silokanals 1910 passierten jährlich gut 12.000 Kähne die einen Steinwurf entfernte Schleuse. Die Brücke vor dem Steintortum, erstmals am Ende des 13. Jahrhunderts erwähnt, war als Klappbrücke konzipiert, da die Kähne sonst nicht durchgekommen wären. Sie war zuletzt nicht nur baufällig, sondern auch gerade einmal sechs Meter breit und somit für den zunehmenden Straßenverkehr ein echtes Verkehrshindernis. Auch, weil sich in unmittelbarer Nähe gleich fünf Straßenmündungen befanden. Gleich mehrere Häuser, darunter auch das historisch wertvolle Torschreiberhaus, wurden kurzerhand abgerissen, um für die 24 Meter breit geplante Brücke Platz zu schaffen.

Der Stadtbaudirektor Moritz Wolf lieferte den Entwurf. Der Auftrag ging an die Berliner Firma Dyckerhoff & Witmann, die zuvor schon die Luckenberger Brücke errichtet hatte. Die Mitarbeiter mussten erst einmal diverse eingerammte Tragpfähle – es waren wohl 170 - und riesige Feldsteine mit bis zu 15 Zentner Gewicht entfernen, um überhaupt erst einmal Baufreiheit zu erlangen. Als es dann so richtig losgehen sollte, streikten erst einmal noch die Zimmerleute. Nach gut vier Wochen ging es dann aber endlich weiter.

Gebaut wurde eine massive Bogenbrücke in Betonbauweise mit Natursteinverblendung. Verwendet wurden rote Quarz-Porphyrsteine, die gut zum mittelalterlichen Steintorturm passten. An der Ufermauer wurde ein zur Tritonengruppe gehöriger Delphin eingelassen. An den Turm kam eine Steintafel. Diese zeigt einen Bienenkorb als Symbol des Gewerbefleißes. Ragende Schornsteine und ein Handelsschiff weisen auf Brandenburgs Industrie, Handel und Verkehr hin. Die Inschrift lautet: „Steintor. Der Steintorturm ward erbaut im Jahre 1380. Die Steintorbrücke ward erbaut im Jahre 1925.“

In den letzten Kriegstagen des Zweiten Weltkrieges wurde die Steintorbrücke zwar stark beschädigt, aber auch schnell wiederhergestellt, so dass sie ab April 1946 wieder voll nutzbar war.