Erstmals urkundlich erwähnt wird die Trostbrücke im 13. Jahrhundert als "pons Trostes" (1266) und als Wechslerbrücke (pons campsorum). Die Trostbrücke stellte zu dieser Zeit die Verbindung von neu gegründeter gräflicher Neustadt über das Nikolaifleet zur bischöflichen Altstadt dar.
Die Trostbrücke in ihrer jetzigen Gestalt wurde 1881-83 nach Entwürfen von Franz Andreas. Meyer erbaut. Die in dem gleichen Zeitraum von Engelbert Pfeiffer geschaffenen Statuen stellen den Erzbischof Ansgar und den Sachsenherzog Graf Adolf III von Schauenburg dar.
Wie die Trostbrücke zu ihrem Namen kam kann bis heute nicht genau bestimmt
werden. In Reiseführern wird vorzugsweise die Deutung beschrieben, dass die
Trostbrücke die letzte Station von zum Tode Verurteilten auf dem Weg zum Galgen
war.
Wahrscheinlicher ist jedoch, dass ein Herr Trost namens gebend war der in der
Nähe gewohnt hat.