Zgrada u kojoj je smešten Muzej se nalazi u centru Novog Pazara. U okviru novopazarskog graditeljskog nasleđa spada u red najreprezentativnijih objekata javne namene. Ne zna se tačna godina njenog podizanja, ali je već sredinom 19. veka u njoj radila ruždija, to jest prva svetovna, državna škola. Prve ruždije su otvarane po Zakonu za opštu prosvetu iz 1869. godine, a jedna se pominje i u Novom Pazaru. Od 1912. godine do kraja Drugog svetskog rata u zgradi je radila osnovna škola, a nakon toga Škola učenika u privredi. Objekat je 1972. godine adaptiran za potrebe Muzeja.
Prilikom radova na hidroizolaciji zidova Muzeja 2002. godine, došlo se do saznanja da zgrada leži nad ostacima starijeg objekta. Urađena su arheološka istraživanja manjeg obima, kojima je obuhvaćeno sondiranje u unutrašnjosti zgrade, prostor ispred i sa zapadne strane Muzeja.
Nakon arheoloških istraživanja došlo se do saznanja da se na mestu sadašnje zgrade, nalazila građevina nepoznate veličine i namene, korišćena tokom 14. i početka 15. veka. Nad njenim ostacima je krajem 16. ili početkom 17. veka podignut hamam.
To potvrđuje nađeni arheološki materijal, kao i podaci koje je ostavio Evlija Čelebi. On u svom Putopisu pominje stari i novi hamam. Stari hamam se i danas nalazi u Staroj čaršiji, dok se novom hamamu nije znala lokacija sve do otkrića hamama ispod zgrade Muzeja. Ceo zapadni zid Muzeja predstavlja ostatke zida hamama, a otkriven je i deo prostorije za kupanje — halvat. Bio je popločan mermernim pločama i imao je banak prislonjen uz zid hamama. Ispod poda prostorije nalaze se masivni zidani stubovi, koji su sastavni deo hipokausta, odnosno sistema za grejanje. Hodnici hipokausta popločani su kamenim pločama, a u samom zidu, su otkriveni „odžaci“ kojima su grejani i zidovi hamama. Iz vremena podizanja hamama nađeni su fragmenti keramičkih tanjira i zdela, komadi okulusa sa prozora, jedna cela i jedna polomljena kurna sa rascvetalom ružom na čeonoj strani klesanoj u plićem reljefu. Ne zna se kada je hamam porušen, a može se pretpostaviti da se to dogodilo u nekom od većih razaranja Novog Pazara, na prelazu iz 17. u 18. vek, ili tokom Prvog srpskog ustanka, početkom 19. veka. Međutim, sigurno je to da je sredinom 19. veka nad ostacima hamama podignuta današnja zgrada. Sa spoljašnje strane ogradnog zida Muzeja se nalazi česma, iznad koje je natpis na turskom jeziku koji glasi: „Ovo je dobro djelo (hajrat) Sjeničaka Sulejmanovića Derviš-bega. Pisano 1. muharema 1309. godine“ — 7. avgusta 1891. godine.