A mai Szabadság tér területe a 19. század második felében még nagyon máshogy nézett ki. Az úgynevezett Újépület, egy hírhedt erőd- és laktanyaszerű katonai objektum állt itt, amelyet II. József császár parancsára építtettek fel, és az 1848–49-es forradalom és szabadságharc bukása után tömeges kivégzőhelyként szolgált.

A kiegyezést követően több ötlet is született a hasznosítására, de végül 1897-ben lebontották. A szomszédságában időközben épülő Országház hatására a környék felértékelődött, ezért úgy döntöttek, hasonlóan reprezentatív épületeket húznak fel itt is.

A Tőzsdepalota és a mai Magyar Nemzeti Bank (akkoriban Osztrák-Magyar Bank) székháza mellett ilyen volt az Adria-palota is, amelyet a Szabadság tér hajójaként is gyakran emlegetnek, mégpedig azért, mert eredetileg az Adria Magyar Királyi Tengerhajózási Rt. központjának épült.

Ez már a kinézetére is rányomta a bélyegét: a homlokzatot csupa vízközeli motívum (pl. delfinek, kötelek) díszíti, valamint a sarki erkélyek is hajóorrot formáznak.

Maga a cég szintén a kiegyezés utáni évtizedekben alakult meg, hogy ne csak osztrák irányítás alatt legyen a Monarchia tengerhajózása. 1891-ig kizárólag teherszállítással – főleg gabonaexporttal – foglalkoztak, egyre messzebb terjeszkedve. Egészen Észak- és Dél-Amerikáig eljutottak, ennek ellenére sokáig csak az állami támogatásnak köszönhetően nem volt veszteséges a működésük.

1891 után lett hivatalosan Királyi a nevük, innentől még több állami támogatást kaptak, így végre saját hajókat is vásárolni tudtak, a teherforgalom mellett pedig a személyszállításba is belevágtak.

Fénykorukban egy brit vállalattal közösen ők üzemeltették a Carpathia gőzöst is, amely a Titanic-katasztrófa után az elsüllyedt hajó több száz utasának életét mentette meg.

A fiumei székház után – itt volt az üzleti központ – pár évvel, 1902-re épült fel a Szabadság téri palota, amely már kinézetében is eleganciát sugároz. Ezt járhattuk most be a Hosszúlépés jóvoltából. A főbejáraton belépve a tágas, márványborítású díszlépcsőházba érkezünk, ami első pillantásra sem mindennapi látvány.

Ezen felsétálva, a szebb napokat látott félemeleten helyezkedtek el az egykori irodák, a szerencsére jobb állapotban fennmaradt első emeleten pedig egy ebédlő, valamint két hatalmas lakosztály kapott helyet, amelyeket a cég vezetői használtak.