W latach 1871–1873 zrealizowano budowę drugiej równoległej linii w kierunku granicy rosyjskiej z Torunia przez Iławę, Olsztyn, Korsze, Gierdawę do Wystruci i dodatkowo linii z Piły przez Chojnice i Starogard Gdański do Tczewa.
W 1880 sieć osiągnęła 2210 km, w 1895 – 4833 km.
Od 1888 wchodziła w skład pruskich kolei państwowych. W 1895 Kolej Wschodnią zarządzaną dotychczas z jednego miejsca – z Bydgoszczy, rozdzielono między trzy obszarowe dyrekcje kolejowe – w Bydgoszczy, Gdańsku i Królewcu.
Obecnie Kolej Wschodnia utożsamiana jest w Polsce zasadniczo jedynie z odcinkiem [Berlin] – Kostrzyn nad Odrą – Gorzów Wlkp. – Piła – Chojnice – Tczew – Malbork – Braniewo – [Królewiec].
Inne linie użytkowane przez Pruską Kolej Wschodnią W wyniku nacjonalizacji lub przejęcia kolei prywatnych sieć Kolei Wschodniej zwiększyła się o: Pomorską Kolej Centralną (Zentralpommersche Eisenbahn) z Runowa przez Złocieniec do Chojnic (przejętą w 1875), Kolej Berlińsko-Szczecińską (Berlin-Stettiner Bahn) lub Kolej Wschodniopomorską (Hinterpommersche Eisenbahn), z liniami Szczecin – Stargard – Koszalin – Lębork – Gdańsk i Białogard – Kołobrzeg (1879)