Die 44,3 km lange Eisenbahnstrecke von Oldenburg (Oldb) Hbf nach Bremen Hbf wurde am 14. Juli 1867 nach dreijähriger Bauzeit eröffnet. Gebaut wurde die Strecke von Großherzogtum Oldenburg. Bremen-Neustadt war die letzte Station auf Oldenburger Gebiet und damit Zollgrenzstation zur Freien Hansestadt Bremen. Von hier aus führt die Bahnstrecke über eine Stahlbrücke nach Bremen. Der Bahnhof wurde von Bremen aus gebaut und von der oldenburgischen Eisenbahn betrieben. Der Bahnhof war auch Aus- und Endbahnhof der Kleinbahn Bremen-Tedinghausen. Von hier zweigte auch die Hafenbahn nach Bremen-Grolland ab. Der erste Bahnhof auf Bremer Gebiet war der Weserbahnhof von 1859.Die Bahnstrecke wurde zwischen 1897 und 1907 zweigleisig ausgebaut.Das 1867 gebaute Empfangsgebäude wurde 1931 durch das heutige aus Backstein gebaute Stationsgebäude ersetzt.