Utemeljena još u XVII. stoljeću, od strane istog vakifa koji je podigao i sahat-kulu, kao glavna, čaršijska džamija. Izvorno je to bila tradicionalna bosanska džamija sa četveroslivnim krovom, te vitkom i visokom kamenom munarom. Pod teretom stoljeća je dosta oronula, pa se u periodu 1914. – 1916. godine pristupilo njezinoj temeljitoj obnovi. Tada je poprimila svoj današnji izgled, a mnogi tvrde da je to jedna od najljepših džamija potkupolnog tipa u našoj zemlji. Nepuna dva desetljeća od izgradnje, doživjela je i svoju prvu obnovu – 1934. godine, kada je nanovo ozidana munara, koja je bila slomljena udarima snažnog orkanskog vjetra, u oluji kakva je u Gračanici ostala neupamćena. Nažalost, munara je ponovo srušena u jesen 1995. godine – agresorskom granatom s Ozrena. Ipak, ubrzo je obnovljena, a njeno je uzdizanje, prve poslijeratne godine, simboliziralo i ponovno rađanje i obnovu Gračanice. U višestoljetnoj povijesti ove džamije, na službi su se smjenjivale na desetine imama, hatiba, mujezina i vaiza, a ostalo je zapisano da je u njoj nekada, još u XVIII. stoljeću, djelovala i javna biblioteka. U dvorištu, odnosno haremu džamije do danas je sačuvan veći broj starih nadgrobnih nišana, neki od njih sa kaligrafski izvedenim epitafima i u stihu ispjevanim tarihima – spomenici kulture sami za sebe.
