Na początku 1956 roku projekt przebudowy stacji był gotowy. Zakładał on rozbicie prac na część torową i budowlaną. Wielkość wyburzeń oceniono na 190 000 m³, a łączny koszt budowy stacji wyceniono na 167 000 tys. zł. Pierwsze dwa perony oddano do użytku w 1958 roku (peron 11 i 12; obecnie 1 i 2). Powstał też tymczasowy pawilon od strony ulicy Stawowej. W czerwcu 1964 roku oddano do użytku zachodnie przejście podziemne, a także pawilon od strony placu Oddziałów Młodzieży Powstańczej. Rok później otwarto peron 13 (obecnie peron 3), a w 1968 roku peron 14 (4) i pawilon od strony ulicy T. Kościuszki. Pod tym peronem znajdowała się hala z poczekalnią i dodatkowymi kasami biletowymi.
W tym samym czasie, w 1959 roku został rozstrzygnięty konkurs SARP na nowy budynek dworca kolejowego, a w ocenie jury praca zespołu „Tygrysów”, w skład którego wchodzili: Wacław Kłyszewski, Jerzy Mokrzyński i Eugeniusz Wierzbicki, została określona jako „wybitnie wyróżniająca się spośród innych opracowań...”. Najwcześniej, bo w 1964 roku powstał pawilon od strony placu Andrzeja. Pod konstrukcję głównego gmachu zburzony został kwartał budynków w rejonie ulic: 3 Maja, Młyńskiej i Stawowej zabudowany eklektycznymi kamienicami. Budowę całego dworca wraz z peronami i przejściami podziemnymi ukończono w 1972 roku.
mały|Dworzec przed rozpoczęciem prac wyburzeniowych mały|Torowisko między peronami 3 i 4 na stacji (przed modernizacją)