Elle a été construite en 1503 ou 1504 (soit 909 après l'Hégire) par Yahya Pacha, un grand dignitaire ottoman. Il était ainsi beylerbey de Roumélie, bey du sandjak de Bosnie, gouverneur de Skopje, vizir, et beau-fils du Sultan Bayezid II. Selon le voyageur et écrivain Evliya Çelebi, la mosquée avait à l'origine une coupole, probablement détruite par le grand incendie de 1689, et remplacée depuis par un grand toit à quatre pentes[1].
La structure en pierre du minaret fait 45 mètres de haut, et la külah (le petit toit conique) culmine à 55 mètres, ce qui en fait le plus haut minaret construit en Roumélie (la région chrétienne des Balkans sous l'Empire ottoman)[1].