Im Jahre 1266 wird das Bauwerk erstmals urkundlich im Stadterbebuch als " pons trostes " erwähnt. Der Brückenname leitet sich vermutlich von einem Kruzifix ab, daß im Mittelalter die Brücke schmückte und den Verurteilten, die diese überquerten, Trost spenden sollte. Zu diesem Zeitpunkt ist die Trostbrücke noch eine einfache Holzbrücke über den Nikolaifleet, als Verbindung der bischöflichen Altstadt mit der gräflichen Neustadt. Symbolisiert wird dieses auch durch die aus rotem Sandstein erstellten Standbildern von Graf Adolf III. von Schauenburg und Bischof St. Ansgar des Bildhauers Engelbert Pfeiffer. Die Trostbrücke wurde beim großen Hamburger Brand 1842 und auch bei den schweren Sturmfluten 1843 und 1847 stark beschädigt, so daß sie schließlich im Jahre 1881 nach dem Entwurf des Architekten Franz Andreas Meyer in Stein erbaut wurde und heute die Verbindung zwischen " Börsenbrücke " und " Neue Burg " herstellt.