Przedostatni ze wszystkich wybudowanych we Wrocławiu normalnotorowych dworców kolejowych, powstał w 1868 wg projektu Hermanna Grapowa, który często mylony jest z Wilhelmem Grapowem, autorem zaprojektowanego kilkanaście lat wcześniej dworca Kolei Górnośląskiej, który dziś nosi nazwę Wrocław Główny.
Już od roku 1855 Kolej Opolsko-Tarnogórska usiłowała uzyskać koncesję na połączenie Wrocławia z Górnym Śląskiem trasą przez Oleśnicę, Kluczbork, Lubliniec, ale koncesję w tym czasie uzyskały Koleje Górnośląskie (zarządzające wówczas wrocławskim Dworcem Górnośląskim, potem Dworcem Głównym). Dopiero w roku 1859 z koncesji tej zrezygnowały i starania podjęły ponownie Koleje Opolsko-Tarnogórskie i - nowo powstałe w 1862 - Towarzystwo Kolei Prawego Brzegu Odry. Koncesję uzyskała ostatecznie 13 listopada 1865 Kolej Opolsko-Tarnogórska, która w 1868 połączyła się z Towarzystwem Kolei Prawego Brzegu Odry, przyjmując nazwę Towarzystwa. Dworzec Nadodrze rozpoczął funkcjonowanie 28 maja 1868 odprawiając i przyjmując pociągi na trasie z Wrocławia do Oleśnicy przez Psie Pole, a 13 listopada tego samego roku uruchomiono docelowe połączenie Wrocław - Fosowskie. Jednym z obiektów inżynieryjnych na trasie do Psiego Pola był stalowy most przez Starą Odrę między Kleczkowem a Karłowicami, zlokalizowany w pobliżu browaru (dzisiejszy Piastowski) i mostu drogowego Hindenburgbrücke (dzisiejszy środkowy Most Warszawski). Początkowo dworzec zwany był Rechte-Oder-Ufer-Thorbahnhof (Dworzec Bramny Kolei Prawego Brzegu Odry), później krócej Breslau Odert(h)or (Wrocław Brama Odrzańska). Wkrótce (w 1872) Towarzystwo Kolei Prawego Brzegu Odry przeprowadziło w północno-zachodniej części ówczesnego miasta (w tym - mostem przez Odrę na jej lewy brzeg, niedaleko starego Mostu Mieszczańskiego) tor łączący Nadodrze z najmłodszym normalnotorowym dworcem miasta (dziś już nieistniejącym) - Dworcem Miejskim Kolei Prawego Brzegu Odry (Rechte-Oder-Ufer-Stadtbahnhof), który stanął obok istniejących już Dworca Świebodzkiego i Dworca Kolei Dolnośląsko-Marchijskiej, w pobliżu dzisiejszych pl. Orląt Lwowskich i ulicy Robotniczej. stalowy most kolejowy nad Starą Odrą między Kleczkowem a Karłowicami na linii z dworca Nadodrze na wschód, przez Sołtysowice i Psie Pole do Oleśnicy
Budynek dworca wzniesiony z czerwonej nieotynkowanej cegły ma długość 190 m nawiązując do modnych w Niemczech lat 60. dziewiętnastego wieku stylów historyzujących. Trójkondygnacyjny korpus dworca posiada trzy ryzality, z czego środkowy, czerokondygnacyjny, poprzedzony jest arkadowym portykiem.
Modernizację dworca rozpoczęto w 1912, a dokończono po I wojnie światowej w latach dwudziestych XX w., przebudowując tunele i perony, a także dokonując zmian w części towarowej.
Po II wojnie światowej, w lipcu 1945, dworzec Nadodrze był pierwszym, który mógł przyjmować pociągi z kierunków wschodnich. Znamienne jest, iż również pierwsza uruchomiona we Wrocławiu linia tramwajowa - nr 1 - połączyła ten dworzec ze stosunkowo najmniej zrujnowanym osiedlem Wrocławia - Biskupinem. Linia ta nadal kursuje po prawie tej samej trasie (dziś już znacznie przedłużonej na północ).
Na placu Staszica przed Dworcem Nadodrze znajdują się również przystanki końcowe regularnych linii autobusowych zapewniających połączenia z miejscowościami leżącymi na północ od Wrocławia; plac ten stanowi w pewnym sensie drugi, mniejszy dworzec autobusowy (centralny dworzec autobusowy miasta umiejscowiony jest w pobliżu dworca kolejowego Wrocław Główny). Do roku 1950 do znajdującego się w pobliżu Nadodrza styku placu Strzeleckiego z placem Staszica dojeżdżała wąskotorowa kolej Wrocławsko-Trzebnicko-Prusicka, której dworzec miejski uruchomiono w 1899. Później (w 1950) stacją końcową tej linii stała się znajdująca się na peryferiach stacja przy ul. Na Polance, a w latach 60. likwidując kolej wąskotorową Wrocław - Trzebnica zamknięto także i tę stację.
