Palatul Rhédey, aflat la colţul Pieţei Unirii cu strada Napoca, are o istorie fascinantă. Clădirea a fost construită în locul pe care se aflau patru case de patricieni clujeni. 

Palatul a fost creat de arhitectul clujean Lajos Pákey, care a fost și arhitect șef al orașului Cluj.

Denumirea oficială a palatului construit în stil eclectic se trage  de la familia care l-a avut în proprietate de la începutul secolului al XVIII-lea. 

Mai mult, prin acest nume, istoria clădirii se leagă și de cea istoria teatrului maghiar din Transilvania, prin sala de bal donată teatrului.

Edificiul era cunoscut însă sub denumirea de ,,Casa cu lanțuri” pentru că era protejat cu lanţuri pe partea dinspre uliţa Fânului, pe unde treceau carele cu fân.

În acea epocă strada Napoca de astăzi se numea ulița Fânului, întrucât din zona complexului Hasdeu până aproape de Mănăștur se întindeau Fânațele Clujului.

În anii 1680-1690 clădirea a fost cumpărată de aristocratul László Székely și renovată de soția acestuia, Sara de Bulușd, fiica unui boier, în 1698.

Această casă a avut și oaspeți de viță nobilă, pe principele Gabriel Bethlen și pe principele ales al Transilvaniei, Francisc Rákóczi al II-lea, care a sărbătorit Paştele din aprilie 1706 la palat. 

Construcția a fost unificată cu alte trei case vecine şi i-a mai fost adăugat un etaj și modificările au fost făcute de proprietarul din vremea aceea, Rhédey János.

Mai mult, clădirea găzduia prima instituţie teatrală maghiară din Transilvania, în noiembrie 1792.

Una dintre primele cafenele din Cluj a fost deschisă aici, în 1875.  Clădirea a devenit în 1899 o casă de raport, cu o zonă de prăvălii. Mai apoi a găzduit sediul Băncii de industrie, casinoul românesc şi primul oficiu de prefectură românesc. 

În perioada comunistă, palatul a fost folosit ca sediu al Consiliului Popular Municipal Cluj. În această perioadă, clădirea a suferit o serie de modificări, care au afectat aspectul original.

La parterul acestei clădiri a funcţionat, până prin anii ’90 Agenţia de voiaj C.F.R.