A kiegyezés után, a mai Budapest területén öt nagy vasúti állomás volt. A személyforgalom növekedése miatt az 1880-as évek elejére egy új fejpályaudvar megépítése vált szükségessé. Az első határozat már 1880-ban megszületett arra vonatkozóan, hogy a következő év őszén el is kezdik az új központi pályaudvar építését. Éppen egy évvel később, 1881. novemberében ki is tűzték a helyét a Kerepesi úti vámnál, az egykori Kerepesi és a Csömöri út kereszteződésében, a mai Baross térnél. Az eredeti tervek szerint már 1883-ra elkészült volna a pályaudvar, de alig egy méternyi mélységben már annyi talajvizet találtak, hogy az alapot meg kellett nagyjából 3000 cölöppel támogatni. Részben emiatt 1882 végén már tudható volt, hogy nem készülnek el vele a következő évre. A bokrétaünnepet 1883. augusztusában tartották, hivatalos átadása – külön ünnepség nélkül – pedig 1884. augusztus 16-án történt.
A főváros a közigazgatási bejárás alkalmával kikötötte, hogy az új pályaudvar homlokzatának a középvonala a Rákóczi út tengelyébe essen. E kikötés folytán a pályaudvari csarnok és a felvételi épület a Baross tér Thököly úti oldala felé tolódott el, az így rendelkezésre álló szűkös terület a vasút számára megnehezítette a vasútüzemi feladatok optimális lebonyolítását.
Az állomást az első években még csak egy kétvágányú pálya kapcsolta az országos hálózathoz. A Józsefvárosi pályaudvar keleti végénél csatlakozó vágányok a Keleti pályaudvar mellett kiszolgálták a Józsefvárosi pályaudvart is, a nyíltvonali elágazási szakaszon hamarosan üzemi zavarok keletkeztek, ezért független bevezetés vált szükségessé.
A nevét hivatalosan egy 1892. szeptember 20-i rendelettel változtatták át az addigi „Budapest-központi pályaudvar”-ról „Budapest-Keleti pályaudvar”-ra. Jelentős esemény volt ez a második névadás: mivel a MÁV 1892-re magába olvasztotta az Osztrák–Magyar Vasúttársaságot, annak pályaudvara is államvasúti lett, ezért veszítette érvényét a „központi” jelző. Bevezették tehát a Keleti és a Nyugati megkülönböztetést, noha a városon belüli elhelyezkedés mellett a kiinduló vonatok iránya már csak részben indokolta ezt a gyakorlatot. A Keleti pályaudvart az évtizedek során több ízben bővítették, átalakították. A vágányok szaporításán kívül egy második mozdonyszín épült, fordítókoronggal, kocsijavító műhellyel és postateleppel. Az első világháború alatt elsősorban a hadiszükséglet kielégítése volt a vasút feladata, ezért a budapesti pályaudvarok megkezdett bővítési munkái megakadtak.
A Keleti pályaudvarnak 1926-ban csak napi 72 vonatpárja volt, a vonatpárok számának takarékosságból való csökkenése miatt, a szerelvényeket több kocsiból állították össze. Hosszúságuk az új típusú, forgózsámolyos személykocsik megjelenésével tovább nőtt.
A pályaudvar szűkös területe miatt a forgalomnövekedést a vágányhálózat átépítésével, új vágánykapcsolatok alkalmazásával tudták megoldani. A pályaudvar vágányai fölé 1931-ben építették ki a felsővezetéket. A pályaudvar vágánycsarnokának acél tetőszerkezetét Feketeházy János tervezte, aki különösen a vasszerkezetek tervezése terén végzett nemzetközi viszonylatban is számottevő munkát. Beosztásánál fogva a MÁV összes hídépítésének felügyeletét is ellátta.
A második világháború idején, Budapest bombázásakor a pályaudvar súlyos sérüléseket szenvedett. Az épület előtti téren 1945-ben fürdőmedence működött, melyet egy évvel korábban eredetileg légoltalmi célra, tűzivíz-tárolónak építettek. Először 1967 és 1970 között az M2-es metróvonal, majd 2004 és 2014 között az M4-es metróvonal építéshez kapcsolódó felszíni tereprendezés során alakították át a mai formájára a teret. A metró és a pályaudvar között aluljárórendszert építettek. Az aluljáró szintjére kerültek a pénztárak és az információk. Az aluljáróból széles lépcsőn lehet feljutni a peronokhoz. (A felújítása 2023 májusára készült el.)
Érdekesség, hogy Sarah Connor német énekesnő ezen a pályaudvaron forgatta legnagyobb slágere, a From Sarah With Love című dal videóklipjét.
Rochlitz Gyula mellszobrát a pályaudvar restijének első vendéglőse készíttette, amelyről sokáig nem tudták, hogy kit ábrázol. A szobrot később az indulási csarnokba helyezték át, ám onnan végleg eltűnt. Az emlékére a MÁV 1959-ben, a pályaudvar megnyitásának hetvenötödik évfordulóján, egy emléktáblát helyezett el az indulási oldalon.
