The Prussian Royal residence was located at Potsdam approximately 25 km west of Berlin, which at the beginning of the 19th century already had more than 200,000 inhabitants. Although railways were already being built in England, the sceptical attitude of the King Friedrich Wilhelm III delayed the establishment of a railway in Prussia. After the opening of the Bavarian Ludwig Railway showed that railways could be operated economically in Germany, it was decided to establish a railway in Prussia. The Prussian Railway Act of 3 November 1838 established the basis for operating private railway companies and also provided for the Prussian state to take them over after 30 years.
The Berlin-Potsdam Railway opened the first section of its line in autumn 1838 (the section between Potsdam and Zehlendorf on 22 September and the main line to Berlin on 29 October). The Potsdamer Bahnhof opened in 1838 just outside the outside Potsdamer Tor (a gate in Berlin’s tax wall). In 1837, the Berlin–Potsdam Railway Company acquired land for the station from the Unity of the Brethren in Berlin and Rixdorf for 12,400 thalers. Its Potsdam station was southeast of the city on the other bank of the Havel river, where it also established a rail workshop. The first railway stations between Berlin and Potsdam were Zehlendorf (established in 1838), Schöneberg (1839) and Steglitz (1839).
The Potsdam-Magdeburg Railway Company (German: Potsdam-Magdeburger Eisenbahngesellschaft) was founded 1845, receiving royal assent on 17 August 1845. It extended the Berlin–Potsdam line to Magdeburg and was later merged with the Berlin–Potsdam Railway to create the Berlin–Potsdam–Magdeburg Railway Company (German: Berlin-Potsdam-Magdeburger Eisenbahngesellschaft).
Although the Potsdam station was directly connected with central Potsdam by the Long Bridge (German: Lange Brücke), the extension of the railway towards Brandenburg over the Havel and on to Magdeburg was very difficult. Directly west of the Potsdam station the line had to cross the Havel and Neustädter Bay, requiring several bridges. In the same section it had to cross the Potsdamer Stadtkanal (Potsdam City Canal, located in the modern Dortustraße), requiring another bridge. The track in this whole section was laid on an embankment. The line from Potsdam Kiewitt (west of Neustädter Bay) to Magdeburg was opened on 7 August 1846, but the Havel crossing was not opened until 12 September 1846, completing the line from Berlin to Magdeburg.
The line had to cross the Havel again near Werder to connect to Werder station on the shore. In order to reach the Elbe station from Magdeburg-Buckau the railway had to cross the Old Elbe, the Taube Elbe, the main Elbe rivers and the island between them containing the district of Werder. Until the completion of the main bridge over the Elbe, the Buckau Railway Bridge, a vertical lift bridge, in 1848 trains terminated at Magdeburg-Friedrichstadt station. By 1847, the trunk line had been largely converted to double track.