Az épület a [[Maiszúri KirályságotKirályság]]ot évszázadok óta irányító Vodejár dinasztia rezidenciája. Az első palota valószínűleg még a 14. században épült meg egy fából készült erőd részeként, ám ez az épület 1638-ban egy villámcsapás következtében megsemmisült. Az épületegyüttest a megmaradó részekből (újabbakkal kiegészítve) [[Kánteráva Naraszarádzsa Vodejár]] építette újjá, [[Csikka Devarázsa Vodejár]] 1704-es halála azonban politikai instabilitást hozott a birodalomban, aminek következében a palota elhanyagolttá vált, sőt, [[Típú szultán]] 1793-ban le is bontatta. A szultán halála után az ötéves [[III. Krisnarádzsa Vodejár]] került a trónra, a koronázási szertartást megfelelő palota hiányában csak egy sátortető alatt tudták elvégezni. Az új uralkodói korszak egyik első feladata volt, hogy új, ezúttal hindu építészeti stílusban megvalósuló palotát építsenek: ez az épület 1803-ra készült el. A sebtében felhúzott létesítmény állaga azonban hamar szintén romlani kezdett, sorsa pedig 1897-ben pecsételődött meg, amikor ''Dzsajalaksmi'' hercegnő esküvőjén tűz ütött ki, aminek következtében a teljes palota leégett.<ref name="tort">{{hiv-web |url=https://www.mysorepalace.gov.in/history.html |cím=A palota története |kiadó=A palota hivatalos honlapja |elérés=2020-11-01 |nyelv=angol}}</ref>
Hogy a város és az uralkodói család ne maradjon méltó rezidencia nélkül, arról a [[IV. Krisnarádzsa Vodejár|IV. Krisnarádzsa]] kiskorúsága alatt a tényleges hatalmat gyakorló [[régens]], [[Kempa Nandzsámmani Váni Vilásza Szannidhana]] gondoskodott: megbízta a híres angol építészt, [[Henry Irwin]]t, hogy tervezzen egy újat. A munkálatok 1897-ben kezdődtek, és 15 év után, 1912-re fejeződtek be. Az építkezés költsége elérte a 4 147 913 [[indiai rúpia|rúpiát]].<ref name="tort"/>
