Egy 1868 decemberében megtartott országgyűlésen döntött úgy a kormány, hogy a forgalom- és utasnövekedés miatt szüksége van a városnak egy központipályaudvarra (nem kapkodták el a döntést, a törvényjavaslat három év alatt jutott el a parlamentig). Az első tervek a Nyugatihoz hasonlóan a Nagykörútra álmodták meg az új vasúti központot: a mai Rákócziút és a körút keresztezését, a volt szemben levő területet szánták neki. Felmerült még a is, ide azonban egy monumentális beruházás eredményeként lehetett volna átvezetni a vasutat a Józsefvárosból, konkrétan az utcák felett egy jó másfél magas viadukton keresztül.
Mielőtt a nagyszabású építkezés megkezdődött volna a Kerepesiúti vámnál (a mai Baross térnél), "közbejött" a gazdasági világválság, ezért jelentőset csúszott a munkakezdés, ami csak 1881-ben indulhatott el. A tervezés feladata RochlitzGyula főmérnöknek jutott, a pályaudvar vasszerkezetét FeketeházyJános hídépítő mérnök elképzelései alapján alakították ki. A tanulmányterv szerint a felső szintre tervezett vonatfogadó csarnokba érkeztek volna a vágányok, az alsó szinten bonyolódott a poggyászforgalom, illetve álmodtak ide postát, kávéházat. A végül a Kerepesi úton megvalósított elképzelések majdnem mindegyike idézte az eredeti terveket. A különbséget többek között az jelentette, hogy nem volt szükség összekötő poggyászalagútra, plusz mivel az utcai és a vasúti forgalom egy szinten helyezkedett el, a díszlépcső helyett az induló és érkező csarnokok közvetlenül csatlakoztak a várótermekhez, továbbá kisebb lett a kávéház.
Rochlitz Gyula külföldi tanulmányútjai során inspiráció gyanánt több európai nagyvárosi pályaudvart felkeresett, így fordulhatott elő, hogy a végül 1884-ben átadott eklektikus stílusú főépület több hasonlóságot mutat a berlini Lehrter Bahnhoffal. A főépület szépsége mellett impozáns méreteivel is lenyűgözte a látogatókat: területe 16 800 négyzetméter, fedett csarnokának hossza 180 méter, szélessége 42 méter, magassága 31,4 méter. Az állomás vágányzata megnyitáskor napi 52 vonat forgalmának lebonyolítására volt alkalmas. Előcsarnokát ThanMór falfestménye, valamint LotzKároly freskói díszítették, az épület főhomlokzatának egyik oldalán JamesWatt, a másikon GeorgeStephenson szobra látható. Felettük a Víz és a Tűz istensége által megszülető Gőz alakja tornyosul közel 32 méter magasságban.
Csodájára jártak az akkor még újdonságnak számító villanyvilágításának is, amit a Ganz gyár által készített 70 ívlámpa szolgáltatott, további 644 izzólámpával együtt dolgozva. A Nyugatival ellentétben szép csendben, pompás nyitóünnepség nélkül adták át a nagyközönségnek 1884. augusztus 16-án, az első szerelvény innen Miskolc felé pöfögött. A korabeli sajtó odavolt érte, Magyarországhoz és Budapesthez méltó épületnek nevezte.
Keleti pályaudvarra történő 1892-es átkeresztelésének története roppant egyszerű. Egyrészt földrajzi fekvése okán kapta, másrészt a fővárostól keletre fekvő Erdéllyel és a Balkánnal fenntartott kapcsolatra utalva. Erre az évre a MÁV bekebelezte az Osztrák–Magyar Vasúttársaságot, így annak pályaudvara is államvasúti lett, tehát érvényét vesztette a "központi" jelző.
A kezdeti években, évtizedekben viszonylag kevés átalakításon esett át. Az I. világháborúig bővítették a vágányok számát és épült egy második mozdonyszín kocsijavító műhellyel kiegészítve. Az első világháború alatt elsősorban a hadi szükséglet kielégítése volt a vasút feladata, ezért a budapesti pályaudvarok megkezdett bővítési munkálatai megakadtak. A háború után jelentősen visszaesett a Keleti forgalma, amely nagyjából jó 15 év elteltével állt vissza a rendes kerékvágásba. A harmincas évek elején felsővezetéket építettek a vágányok fölé, ezt követően érte el a pályaudvar forgalma az akkori csúcspontot. 1940 decemberére datálódik a pályaudvar történetének talán legemlékezetesebb balesete, ekkor egy csarnokba betolató szerelvény fékhiba miatt nem tudott megállni és a bakot kiütve a bejárati kapun keresztül kigurult a Barosstérre, ahol a bejárati lépcsősoron állt meg. Személyi sérülés nem történt.
Fajsúlyosabb építkezések a károk helyreállítása végett a II. világháborút követően történtek. Ide kapcsolódik, hogy 1945-ben még légoltalmi céllal fürdőmedence működött a pályaudvar előtti téren. Meglehetősen durva háborús csapások érték az épületet: romokban hevertek a várótermek és a csarnokok, kiégett az érkezési oldal. Az évekig tartó munkálatok során felhúzták többek között a mai nemzetközi jegypénztárakat.
A háború következményei jelentősen betettek az utazási igényeknek, például a Keleti egészen a hetvenes évekig kénytelen volt erőn felüli utasmennyiséget szállítani/fogadni. Az 1960-as évek újabb átalakításokat hoztak: lett étterem, új órát komponáltak a homlokzatba, de ami ezeknél is fontosabb, az évtized végére a 2-esmetró építésével kialakították a metró és a pályaudvar közötti aluljárórendszert, melynek szintjére kerültek a pénztárak és az információk, az aluljáróból széles lépcső vezetett a peronokhoz.
A csarnokban eredetileg meglévő öt vágányt az 1980-as évekbeli tervszerűsítésnél négyre csökkentették, majd a további felújításokat követően üzembe állították a teljesen automatizált váltóállító-rendszert az időközben műemléki védettség alá helyezett épületben. 2004-re teljesen kicserélték a teljes födémszerkezetet és korszerűsítették a tetőt, 2008-ra pedig belső felújításon is átesett a pályaudvar. A 4-es metró építése miatt hosszú évekig kordonok "díszítették" a Keleti előtti Baross teret, ez idő alatt még egy épülethomlokzati felújítás is belefért. A zöld metróvonal itteni állomásának átadása 2014. március 28-án történt meg.
Napjainkban a Keleti pályaudvar Magyarország legforgalmasabb közlekedési csomópontja, ahol naponta 410 vonat közlekedik és a pályaállapotok is itt a legjobbak.
