Der Grundstein des Bahnhofes in Cuxhaven wurde am 4. Mai 1881 gelegt. Der Bahnhof war, wie die übrigen Gebäude der Strecke, nach dem Einheitsplan erbaut worden. Die Gleise verliefen seitlich am Gebäude vorbei. Zum Unterhalt der Lokomotiven gab es einen kleinen, zweiständigen Lokschuppen, außerdem wurde ein Güterschuppen und ein Stellwerk errichtet.
Mit der Eröffnung der Strecke nach Geestemünde 1896 war der alte Bahnhof den Anforderungen des Zugverkehrs nicht mehr gewachsen. Der heutige Stadtbahnhof in Kopflage wurde gebaut und am 30. Mai 1898 feierlich eingeweiht. Einen Tag später wurde der reguläre Betrieb aufgenommen. Das alte Bahnhofsgebäude von 1881 wurde 1910/11 um ein Stockwerk erhöht. Es ist bis heute erhalten und diente der Bahn sowie zeitweilig auch der Bahnpolizei als Dienstgebäude.
Beide Bahnhofsgebäude wurden im Laufe der Jahre immer wieder umgebaut, blieben aber in ihren Grundzügen bis heute erhalten. Der Bahnsteig für die Hamburger Züge erhielt 1903 eine Überdachung.
1928 gab es in Cuxhaven neben dem alten Lokschuppen aus den ersten Betriebsjahren bereits den großen Ringlokschuppen und einen eigenen Wasserturm für das Bahnbetriebswerk Cuxhaven, das im Mai 1960 aufgelöst wurde. Dem BW Cuxhaven unterstand übrigens auch der Lokbahnhof Bremervörde. Die Drehscheibe und der Lokschuppen wurden 1983 abgerissen. Zum Ausbau der Drehscheibe reiste eigens der Kranzug “Niedersachsen” an. Das vierte Bahnhofsgleis war 1976 noch vorhanden, wurde vermutlich in den 1980er Jahren entfernt. Die beiden mechanischen Stellwerke “Cf” und “Cs” wurden 1935 gebaut. Damals wurden die Gleisanlagen des Bahnhofsgeländes erweitert, um den neuen Fischversandbahnhof anschließen zu können.