Korábban a posta számos, többnyire alkalmatlan helyen (például a mindenkori postamester lakóházában) működött. A megnövekedett forgalom miatt, és a megfelelő színvonalú szolgáltatás érdekében építették fel a központi postaépületet, amelyet azóta többször bővítettek, felújítottak. A Postapalota homlokzati terveit Wälder Gyula (a Zenepalota tervezője) és a többi részét Szörényi-Reischl Gusztáv készítette, a kivitelező Árva Pál építési vállalkozó volt. Az épület homlokzata a mai Hősök terére néz (akkoriban még földszintes épületekkel beépített terület volt), bal oldalon a Horváth Lajos utcába benyúlt egy szárnya, jobb oldalon pedig a Pece-patak határolta. 1944 késő őszén, amikor a németek már visszavonulóban voltak, fel akarták robbantani. A miskolci postások azonban a rengeteg alkatrészt, készüléket ládákba csomagolva kimentették, az elhelyezett aknákat pedig hatástalanították – megmentve az épületet és berendezését a pusztulástól.
A Postapalotát fennállása óta háromszor is bővítették, legutóbb 1995–96-ban.
