Pierwszą kolejką w Nowej Marchii była kolejka Kostrzym - Krzeszyce. Otwarto na niej ruch 0512.1896, najpierw na odcinku Kostrzyn - Słońsk (14.6) kilometra.
Punkt początkowy kolejki mieścił się na obecnej stacji Kostrzyn.
Firmą która budowała i eksploatowała kolejkę była firma Lanz & Co.
21.10.1906 przedłużono linię do Krzeszyc ( 29.92. kilometra).
05. 01. 1915, poprowadzono ją do stacji Rudnica, gdzie połączono ją z linią
Gorzów – Sulęcin. Całkowita długość linii wynosiła teraz 42.72 kilometra.
Przebiegała ona na prawym brzegu doliny Warty, co umożliwiło jej korzystne trasowanie.
Obsługiwała 5 prywatnych bocznic.
Dwa razy w tygodniu między Berlinem a Słońskiem z uwagi na istniejące w Słońsku więzienie kursował wagon więźniarka.
Początkowo jeździły po niej dwu osiowe parowozy firmy Vulkan.
Po przedłużeniu linii potrzebowano silniejszych parowozów.
W obrębie kolei Lenza dwie lokomotyw Ot wymieniono na Ct odpowiadające z grubsza pruskim T3.
W roku 1908 wpływy wynosiły 163 589 Marek, wydatki 100 768 Marek.
Wypłacono 3, 5 % dywidendę.
Zatrudniano 14 urzędników i 5 robotników. Przed wydłużeniem linii do Rudnicy zwiększono liczbę parowozów o dwa dobre Ct, zbudowane w 1915 roku przez O & K ( F.N o numerach 7141 i 7142).
Odpowiadały one również pruskim T3.
Początkowo eksploatowano prawdopodobnie 3 wagony motorowe, 3 osobowe, 1 pocztowy oraz 1 roboczy.
Pomimo pierwszej wojny światowej nie brakło planów dalszego przedłużenia linii w kierunku wschodnim.
Jako punkty końcowe rozpatrywano Drezdenko, Krzyż, Drawski Młyn, Miały ( na linii Krzyż - Poznań ).
Z tymi projektami wiązało się jednak wydłużenie linii o dobre 60 - 70 kilometrów, na co raczej nie pozwalała zbyt małą ilość posiadanego taboru.
Ponadto w 1919 roku Miały oraz Drawski Młyn znalazły się poza granicami państwa.
Jednak brakowało środków na połączenie z Krzyżem .
W tym czasie firma Lenz przekazała kolej do Dyrekcji Ruchu Kolejowego, w Brandemburgii w Berlinie.
W 1926 roku nabyto jeszcze jeden parowóz Ct.
W 1934 roku Kupiono jeszcze jeden krótki 4 osiowy wagon motorowy z DWK, który w 1939 roku był tak intensywnie eksploatowany, że warto przypomnieć o późniejszym sprowadzeniu na kolejkę jeszcze jednego wagonu motorowego.

Eksploatacja kolejki przez Niemców zakończyła się najpóźniej 01.02.1945 roku w czasie natarcia sowieckiego.