Située sur une petite colline, elle domine le bazar et c'est l'une des plus belles et plus grandes mosquées macédoniennes. Elle a été construite pendant la dernière décennie du XVe siècle par Mustafa Pacha, un dignitaire qui a vécu pendant les règnes de Bayazid Ier et Selim Ier[1].
La cour de la mosquée compte un turbe hexagonal décoré de marbre et couvert d'une coupole, endommagé par le tremblement de terre de 1963[1]. Ce turbe renferme encore le sarcophage d'Umi, l'une des filles de Mustafa Pacha. Autrefois, la cour comptait aussi un caravansérail, une médersa, un imaret (cantine populaire) et un mekteb[2].
La mosquée est une construction austère, composée d'un élément principal à coupole unique et d'un porche supporté par quatre colonnes et couvert par trois petites coupoles. L'ensemble est décoré de sculptures en stalactites et d'éléments en bois[2].