Trunk line

Prolonged negotiations were conducted regarding the route between Cologne and Dortmund. Interested parties from Bergisches Land and the Wupper valley supported a direct route through the local hills. This was rejected by the company because of the high costs for the necessary engineering works. On 18 December 1843, the Prussian government granted a concession to the CME for the line from Deutz (now a suburb of Cologne) through Mülheim am Rhein, Düsseldorf, Duisburg, Oberhausen, Altenessen, Gelsenkirchen, Wanne, Herne and Castrop-Rauxel to Dortmund and on to Hamm, Oelde, Rheda, Bielefeld and Herford to Minden. This route bypassed the old mining areas but travelled through more open terrain. This route is similar to that advocated by the economist Friedrich List in 1833. The decisive factor favouring the route north of the Ruhr was the influence of David Hansemann, who was then briefly Prussian Minister for Finance. The Prussian state acquired one seventh of the share capital of the company at its foundation.

The first section from Cologne to Düsseldorf (Cologne–Duisburg) was opened on 20 December 1845. Only a few weeks later, on 9 February 1846, the second section was completed to a temporary terminus at the site of present-day Duisburg Hauptbahnhof called Duisburg Cologne-Minden station, the first of three train stations built at the same site. The next sections (Duisburg–Dortmund and Dortmund–Hamm lines) were opened on 15 May 1847. On 15 October 1847 the last section to Minden (Hamm–Minden line) was opened, thus completing the entire 263 kilometre long, single track railway. On the same day the Royal Hanoverian State Railways opened its Hanover-Minden Railway, completing a connection to Berlin and northeastern Germany.

Branch line to Duisburg-Ruhrort

In 1848 the CME built a branch line to the docks at Ruhrort from Oberhausen station and agreed with the Aachen-Düsseldorf-Ruhrort Railway Company (Aachen-Düsseldorf-Ruhrorter Eisenbahn-Gesellschaft) to construct the Ruhrort-Homberg train ferry.

Cathedral Bridge

The government had pressed the company since the early 1850s to build a railway bridge over the Rhine in Cologne. Because it was not yet possible to build strong bridges with spans of over 100 metres, it was initially planned to build a bridge capable of carrying individual carriages pulled by horses. This was intended to avoid the unloading of cargo on to ferries and its reloading on the other side.

It was then decided during the Cathedral Bridge's construction to build a two-track bridge capable of supporting a locomotive, which had a swing bridge (which could be disabled in the event of war) on the west bank. This was required by the military, which had to give its consent for all bridge projects. It was a truss bridge with spans of 131 and 101 metres.

The foundation stone for its construction was laid by King Friedrich Wilhelm IV on 3 October 1855. It was opened in 1859 and was the second rail bridge over the Rhine, together with a road bridge that had been built in parallel. The first railway bridge across the Rhine had opened in the same year far upstream at Waldshut, which had spans of only 52 metres at most.

The bridge was demolished and replaced by the Hohenzollernbrücke between 1907 and 1911.

Holland line

The next line to be opened was the 73 km-long Holland line from Oberhausen via Wesel and Emmerich to the German/Dutch border at Elten and on to Arnhem. It was put into operation in sections from 15 February to 20 October 1856. The CME left operations on the section from Emmerich to the border of to the Dutch Rhine Railway Company (Dutch: Nederlandsche Rhijnspoorweg-Maatschappij, (NRS).

Cologne-Gießen Railway

The Cologne-Minden Railway Company built the 183 kilometre long railway between 1859 and 1862 from Deutz via Betzdorf, Dillenburg and Wetzlar to Gießen, with a branch to the mines in Siegen. In Siegen, it connected with the Main-Weser line. This line now forms the northern part of the Sieg line, the Heller Valley Railway and the southern part of the Dill line.

Paris–Hamburg or Hamburg–Venlo railway

At the end of the 1860s the Cologne-Minden Railway Company built its largest project, when Prussia decided that the section of a French railway company's project for a line from Paris to Hamburg (called the "Paris-Hamburg line") in Germany would need to be owned and operated by a German railway company. The Cologne-Minden Railway Company won the tender to build the approximately 550 kilometre long Hamburg-Venlo line against the competition of the Rhenish Railway Company. The cost of its construction was calculated to be 43 million thalers.

The Cologne-Minden Railway Company had reserved the right to connect the proposed line from Venlo via Wesel, Münster and Osnabrück to Bremen and Hamburg to its existing line between Cologne and Minden. Therefore, on 1 January 1870 it began construction of a new line between the two routes from Wanne-Eickel to Haltern. During the Franco-Prussian War large parts of the line were temporarily put into operation: On 1 January 1870 to Munster, on 1 September 1871 to Osnabrück, on 15 May 1873 to Bremen-Hemelingen. On 1 June 1874, the line was completed.

The line south towards Venlo reached Wesel on 1 March 1874, but was delayed by the need to build the longest railway bridge in Germany over the Rhine Bridge at Wesel, which was opened on 31 December 1874. During the planning phase had been argued that no financial return could be expected from this section. So not surprisingly the section Venlo–Straelen was closed at the initiative of the Dutch Railways on 3 October 1936. The rest between Straelen, Wesel and Haltern is also now largely closed. On the other hand, the line from Wanne-Eickel to Hamburg is one of the busiest railway lines in Germany, however, and is now sometimes referred to as the Rollbahn ("rolling line").

Emscher Valley Railway

From 1871 to 1878 the CME built another line from Duisburg to Dortmund along the Emscher valley largely parallel to its trunk line via Osterfeld Süd and Wanne through the northern Ruhr to service the growing industries and prosperous coal mines.