Mezi někdejší Koňskou a Novou bránou vznikla v letech 1870-1871 nádražní budova, kterou v novorenesančním slohu navrhli arch. Antonín Barvitius a Vojtěch Ignác Ullmann. Průjezdnost nového nádraží podmiňovalo vybudování tunelu pod Vinohrady, což se také stalo. První vlak sem přijel 14. prosince 1871 z Vídně a přivezl devět cestujících.
Nádraží, které bylo zpočátku na počest císaře Františka Josefa I. nazváno jeho jménem, přestalo po čase kapacitně vyhovovat. Proto byla v roce 1899 vypsaná architektonická soutěž na novou nádražní budovu, včetně radikálního rozšíření kolejiště a nástupišť. Ze soutěže vyšel vítězně návrh arch. Josefa Fanty. Podle něho bylo nádraží v letech 1901-1909 komplexně přestavěno. Vyrostl tu objekt v tehdy módním architektonickém slohu, secesi. Střed celé mohutné stavby tvořila odjezdová hala s kopulí, po stranách stály dvě patrová boční křídla s provozními prostorami, zakončenými vyššími věžovitými budovami.
Můžeme tak konstatovat, že nádraží má celkem čtyři věže, z nichž dominantní jsou dvě po stranách hlavní dvorany. Jejich vrcholky podpírají nazí Atlanti, jimž chybí i pověstný fíkový list a jejich nahota urážela tehdejší mravokárce. Jelikož obnaženého lidského těla jako výtvarného motivu bylo použito i v interiérech, někteří jednotlivci označili toto nádraží za nemravné.
Málo známý je fakt, že po roce 1922 v jedné z věží nádražní budovy provizorně sídlila Česká astronomická společnost. Pozorování nebeských těles tu však pro kouř z lokomotiv nebylo prakticky možné, a proto astronomové věž záhy opustili.
V letech 1972-1977 byla Fantova historická budova nádraží doplněna o moderní třípodlažní odbavovací halu, jejímž hlavním projektantem byl architekt Josef Danda.
