A közhiedelem szerint Lillafüred névadója gróf Bethlen András földművelésügyi miniszter volt, aki 1892-ben Vay Lilla úrhölgy tiszteletére keresztelte el az egyik vadászat során felfedezett, lenyűgöző szépségű helyet. Az esemény által felkelt az érdeklődés a környék iránt. A következő évben megindult az Erzsébet sétányon – több villával együtt – a Lilla szálló építése (a második világháborúban leégett).
Az üdülőteleppé fejlesztés gondolata az 1920-as években, gróf Bethlen István miniszterelnökben fogalmazódott meg. Első lépésként a Hámori-tavon fából kiépített strandot hoztak létre. Mivel a tó vize hideg volt, meleg víz után kezdtek kutatni, de az erre a célra, a mai Szent István barlanggal szembeni autóbusz parkoló helyén, mélyült kutató fúrás nem hozott sikereket.
A környék szépsége és természeti adottságai késztették Bethlen István miniszterelnököt arra, hogy felvesse egy olyan kormányüdülő megépítését, ahol a nemzetközi kapcsolatokat fogadásokkal egybekötve ápolhatják. A javaslat miatt Bethlent sok bírálat érte, mivel a ‘20-as évek végének nemzetközi gazdasági válsága Magyarországon is súlyos helyzetet idézett elő, így a szálló építéséhez szükséges hatalmas beruházások esztelennek tűntek.
Mindezek ellenére a szálló építéséről döntés született, a tervezéssel Lux Kálmánt, a neves építészt bízták meg. Lux a szállót az 1400-as évek végének stílusában álmodta meg, idézve a Mátyás-korabeli paloták hangulatát. A tervek tartalmazták az épület környékének kialakítására vonatkozó elképzeléseket is.
A függőkert létrehozása és a parkosítás mellett nagy költségeket emésztett fel az is, hogy a téli sportok kedvelői részére a Mária sétány felett ródli- és bobpályát, ettől nem messze felvonóval ellátott sípályát, a fehérkő-lápai fennsíkon versenyek rendezésére is alkalmas síugró sáncot építettek ki.
A szálló helyén 22 felső-hámori családi ház állt, melyeket kisajátítottak és a tulajdonosok számára a községben újakat építettek. Sokáig húzódtak a tárgyalások a Weidlich-villa tulajdonosával (ma Tókert Panzió), aki még fiumei csere-villáért sem volt hajlandó lemondani házáról. A szálló eredeti terveit ezért módosítani kellett, és emiatt került jelenlegi nyomvonalára az országút is.
A szálloda építése 1927-30 között zajlott. Az építés folyamata a gazdasági válság idején a jól szervezett közmunkák egyik leglátványosabb példája volt, amelyről a túl költségesnek vélt beruházás ellenzői is elismerően nyilatkoztak. A Palota átadására – Horthy Miklós kormányzó és Bethlen miniszterelnök nélkül, viszonylag szerény keretek között – 1930. június 7-én került sor. A visszafogottságot az indokolta, hogy a sajtó részéről a kormányt sok támadás érte a tékozlónak minősített építkezésért, ezért nem akarták a költségeket fényűző megnyitással növelni. Ennek ellenére rengeteg vendég, - sok külföldi is – érkezett a megnyitóra. A sikeres nyitást óriási érdeklődés követte. Autók hosszú sora kígyózott a Lillafüredre vezető szerpentinen, és vonattal is nagyon sok látogató érkezett. A szálloda hamar a luxusvendégek kedvelt tartózkodási helye lett. Lillafüred, mint klimatikus üdülő- és gyógyhely vált ismertté.
Az idegenforgalmi prospektusokban légúti- és neurotikus betegségekre ajánlottak kezelést. A magaslati klíma mellett fekvő- és terepkúrák, szénsavas oxigénfürdő, habfürdő, iszappakolás szolgálták a gyógyulást. Ezeket a kezeléseket a Felsőhámorban lévő gyógyfürdőházban végezték, amelynek ma már csak a helye ismert.
A turisztika és sport kedvelőinek szervezett kirándulásokat, lovaglást, vadászatot ajánlottak. A Hámori-tavon horgászatra, úszásra, evezésre, vitorlázásra nyílt lehetőség. A télen érkezők igénybe vehették a ródli- és bobpályát, illetve a műugró sáncot. A sípályán síoktatás folyt. Az 1930-as évek végéig nyaranta a szálló folyamatosan teltházzal üzemelt. A téli hónapokban azonban – a sport kínálat ellenére – viszonylag elhagyatott volt.
Felmerült a szállóban egy játékkaszinó létrehozásának terve is. 1934-ben németországi tőkések tettek ajánlatot ennek megvalósítására. A magyar állam azonban elzárkózott a javaslat elől, bár ez az államkincstár számára jelentős bevétel lehetett volna.
A ‘30-as években a szálloda több rangos rendezvénynek is otthont adott.
1930-ban a Bankok Egyesülete a szállóban Pénzintézeti Kongresszust szervezett.
1931 júniusában itt rendezték meg az első Magyar Filmhetet, melyet nagy nemzetközi érdeklődés kísért. A rendezvény alkalmából sok neves színész és hazai előkelőség érkezett. Ugyanebben az évben, szeptemberben nemzetközi teniszversenyt szerveztek. 1933 júniusában 200 résztvevővel itt zajlott le az Írói Hét, amin részt vett József Attila is, és a környék szépsége ihlette az Óda nagyszerű sorainak megfogalmazására. A találkozót tragikus esemény, az írószövetség elnökének váratlan halála szakított félbe. Minden évben kiemelkedő eseményt jelentettek az Anna bálok, melyek fényűző keretek között, óriási részvétellel zajlottak.
Az üzemeltetés a megnyitást követően hosszú időre az állam kezében maradt.
A gazdasági válság miatt a Földművelésügyi Minisztérium kedvezőbbnek tartotta volna a szálló bérbe adását, ezért az üzemeltetésre pályázatot írtak ki. Több érdeklődővel folytatott hosszú tárgyalások után a bérbeadási kísérlet sikertelen maradt, így a szálló továbbra is állami tulajdont képezett.
A második világháborúban a Palotaszállóban hadikórházat rendeztek be a sebesült orosz katonák számára. Bár a háború alatt az épület maga nem rongálódott meg jelentősen, a kórházi üzem és a lopások helyrehozhatatlan károkat okozott az eredeti fényűző berendezésben. A háború után az üzemeltetési jog a Bükki Gyógyfürdőkre, majd a Szakszervezetek Országos Tanácsára szállt. A szálloda ezt követően 40 évig SZOT üdülőként üzemelt, ahol beutalt dolgozók kaptak elhelyezést. Ez az állapot erősen hozzájárult a minőség további romlásához. A berendezés nagy részét olcsó, igénytelen bútorokra cserélték, és az átépítések is a nagyobb vendégszám kevésbé igényes kiszolgálására irányultak. 1974-től 1977 decemberéig az épületben felújítás zajlott, ezalatt a Palotaszálló nem fogadott vendégeket.
1992-ben a Palotaszálló a Nemzeti Üdülési Alapítvány tulajdonává vált, amely a szálló üzemeltetését 1993-ban a Hunguest Részvénytársaságon belül megalakult Toboz Regionális Üdültetési Kft. Hatáskörébe adta. 1994-ben a Lillafüred Alapítvány a szállóban képzőművészeti galériát hozott létre, ahol a havonta változó kiállítás megnyitókat koncertek kísérték. 1998-ban a Hunguest Rt. nagyszabású felújítást végeztetett a szállodában, melynek során a szobákat új burkolattal és bútorzattal látták el, a társalgót patinás stílbútorral rendezték be, új belsőépítészeti megoldásokat alkalmaztak. A szálló a korábbi egycsillagos helyett háromcsillagos lett. Az európai színvonalú sport-fitness centrum létrehozásával nagymértékben bővültek az aktív pihenésre lehetőséget nyújtó szolgáltatások.
A 2009 májusában kezdődött felújítási munkálatok során tágas, az épület stílusához alkalmazkodó bútorzattal rendelkező szobákat alakítottak ki. Valamennyi szoba kényelmes, hangulatos fürdőszobával felszerelt, szobáinkban színes televízió és minibár biztosítja a vendégek zavartalan és teljes kikapcsolódását. A szobai telefon és az ingyenes Wifi vendégszobai Internet lehetővé teszi az üzleti utazók igényeinek teljes körű kiszolgálását is.
A szálloda wellness részlegében a már meglévő szolgáltatások köre és a részleg alapterülete is kibővítésre került. Az új „Csendes Wellness” 08.00-09.00 és 19.00-21.00 óráig kizárólag 14 év feletti kedves vendégeink részére áll rendelkezésre, 09.00 és 19.00 óra között azonban 14 év alatti gyermekek kikapcsolódását is szolgálja.
Szállodánk 2023. április 1-jétől változatlan vendégszeretettel, megújult arculattal és Hotel Palota Lillafüred**** néven már teljesen önállóan várja új és visszatérő vendégeit a mesés Lillafüreden.