Eine solche Bahnverbindung lag im Interesse beider Staaten. Bremen war eine schnelle Anbindung seines Vorhafens wichtig und Hannover musste, um den eigenen Hafen in Geestemünde zu fördern, eine gute Hinterlandanbindung schaffen. Als am 28. Februar 1859 „(…) wegen Anlegung einer Eisenbahn von Bremen nach dem Ausflusse der Geeste“ zwischen Bremen und Hannover ein Vertrag geschlossen war, hatten langjährige Auseinandersetzungen der beiden Staaten um die geeignetste Trassenführung ihren Abschluss gefunden.
Während Bremen den kürzesten Weg zwischen der Hansestadt und ihrem Außenposten an der Wesermündung bevorzugte und die Strecke durch die Dörfer der Osterstader Marsch legen wollte (die wurden später durch die Niederweserbahn erschlossen), hatte Hannover ganz andere Interessen: Hier sollten mit der Bahnstrecke möglichst viele Orte Anbindung an das wachsende Schienennetz erhalten und die Trasse deshalb in einem Bogen über Beverstedt führen. Außerdem gab es Pläne, später in Beverstedt eine Strecke Richtung Harburg anzuschließen. In den Wintermonaten, wenn der Hamburger Hafen wegen Eisgangs nicht zu erreichen war, wollte man Geestemünde als eisfreie Alternative anbieten können und dadurch zusätzliche Verkehrsleistungen anziehen. Bereits im Juni 1856 war für Hannover die Sache klar, die Trassenführung genehmigt und die Baukosten ab August bewilligt.
Wer in diesem Streit die stärkere Position hatte, stand schon von vorne herein fest. 1851 hatte Bremen bei Verhandlungen über eine Gebietserweiterung Bremerhavens gewünscht, einen Bahnanschluss zu bekommen. Hannover hatte daraufhin den Bremern nur eine Zweigbahn zugestanden. Der Bahnhof werde dort gebaut, wo es vor allem Geestemündes Interessen diente, hieß es aus Hannover. Nicht anders sah es bei den Verhandlungen über die Streckenführung aus, so dass die Bremer zu Kompromissen bereit waren. Sie schlugen eine Trasse entlang der Chaussee von Bremen nach Geestemünde vor, die etwa in der Mitte zwischen den beiden anderen Varianten lag. Die letztendlich beschlossene Linie lag dann noch etwas weiter östlich, ließ aber Beverstedt außen vor.
Anfang 1858 drohte das Projekt der „Bremen-Geeste-Bahn“, wie die Strecke nun genannt wurde, kurzfristig doch noch zu scheitern. Bremen wollte entgegen anderslautender Verträge am Betrieb der Bahn teilhaben. Erst als Hannover daraufhin androhte, die Bahn alleine zu bauen, wurde am 28. Februar 1859 im beiderseitigen Einvernehmen der Staatsvertrag geschlossen, der den Bahnbau besiegelte. Die Strecke sollte nun vom Bremer Hauptbahnhof über Walle, Oslebshausen, Burg, Ritterhude, Osterholz, Lübberstedt, Stubben nach Geestemünde führen, von wo eine Zweigbahn nach Bremerhaven vorgesehen war. Zugleich wurde der Bau einer Nebenbahn von Bremen nach Vegesack in das Gesamtprojekt einbezogen. In Geestemünde war die Anlage eines Kopfbahnhofs geplant. Die Baukosten für die Strecke bis Geestemünde trugen beide Staaten zu gleichen Teilen, ebenso wie die Verwaltungskosten. Für die Zweigbahn gab es besondere Regelungen. Sie sollte ausschließlich dem Güterverkehr dienen. Eine Ausnahme war nur für Auswanderer-Sonderzüge vorgesehen. Die Finanzierung wurde geteilt: Von Geestemünde bis zum Geesteufer zahlte Hannover, die teure Drehbrücke über den Fluss und das Reststück musste Bremen aus eigener Tasche finanzieren.