A tatárjárást követően, a mai Rudas fürdő helyén a johannita lovagok építettek először ispotályt és fürdőt. Az ispotály a török hódításkor még vélhetően állt, amit a törökök átalakítottak és fürdőként használtak saját fürdési kultúrájukhoz alakítva. Valószínűleg Ali budai pasa kezdte meg az eredeti fürdő javítgatását, majd Szokoli Musztafa, akinek nevéhez több török kori budai közintézmény létrehozása is kapcsolódik, 1566–1572 között újjáépítette.
A török fürdő nyolc szögletű medencéje és nyolc oszlopos medencetere ma is a Rudas fürdő épületének magja. Az oszlopok tartják a felülvilágítókkal áttört félgömb kupolát, ami a fürdő ékköve. A fürdő török kori nevét („Zöld oszlopos fürdő”) minden valószínűség szerint azért kapta, mert a kupolát tartó oszlopok közül az egyik zöld volt. Nevének kialakulásáról több elgondolás is felvetődött: egyes vélemények szerint ugyanis az elnevezés a fürdő vendégeit Pestről Budára szállító komp rúdjával hozható kapcsolatba. Az is elképzelhető, hogy a fürdőt Buda visszafoglalása után a tabáni szerbek és bosnyákok bányafürdőnek (Rudna ilidzse) nevezték, és így a Rudas a rudna szóból ered.
Buda visszafoglalása után a királyi kamara a fürdőt a városnak adományozta. A XIX. század elején pedig a Rudas fürdő már a társasági élet középpontja, a város előkelő közönségének találkozóhelye. Több apró átalakítás után Dankó József tervei alapján 1831-ben fejezték be átépítését. Buda városa egy 15 szobából álló „vendég-szállást” és a török fürdőhöz csatlakoztatva kád- és kőfürdőt építtetett. (A szálloda klasszicista épületrésze sajnos 1944-ben elpusztult.)
Újabb átépítést követően 1866-ban megnyílt a Rudasfürdő és Gyógyintézet. Buda város közgyűlése ekkor tiltotta meg, hogy férfiak és nők a fürdőt közösen használják.
A fürdő 1894-ben megnyitott úszócsarnokát csak a nyári hónapokban üzemeltették, mert a forgalom a téli időszakban meglehetősen gyér volt. Az uszoda részt 1930-ig a férfiak és a nők csak felváltva vehették igénybe. A Rudas fürdőt 1933-ban nyilvánították gyógyfürdővé.
1936. novemberében a főváros közgyűlése hozzájárult a rádiumos kádfürdőhelyek számának kibővítéséhez. Külön orvosi kezelőket létesítettek, továbbá növelték a szállodai férőhelyeket, így az épületrész ekkor 23 szobával „gyógyszállóként” működött.
Az épületet, amelyet a II. világháború alatt súlyos bombatalálat ért, Tőkés György tervei alapján 1951-ben és 1952-ben újjáépítették.
A 2004-ben az átépítési munkálatok előtt az épület műemléki jellegére és a törvényi előírásokra tekintettel minden épületrészre kiterjedő régészeti feltárást végeztek. A régészek a medencetér falában a falak mentén körbefutó padka nyomára bukkantak. Ez azt bizonyította, hogy a török korban csak a mai nagymedence létezett. A falak kutatásánál felszínre kerültek a török kerámia vízvezetékek is, amelyek a medencébe és a csorgókutakba vezették a vizet, ahonnan kis kőmedencékbe folyt tovább. Az udvari részen egy barokk malom falait tárták fel, amely már egy 1712-es rajzon is szerepel.
