Klubi u themelua në vitin 1928, nën emrin KF Sanxhak, i cili më vonë ndryshoi në KF Dezheva. Klubi ka luajtur nën emrin e tij aktual që nga viti 1962, kur KF Dezheva dhe një klub tjetër lokal futbolli, FK Ras, u bashkuan nën emrin FK Novi Pazar. Gjatë viteve 1980 dhe 1990 klubi ishte magnet për shumë nga lojtarët e talentuar shqiptarë të Kosovës si Nazmi Rama, Naser Salihu, Mentor Miftari, Sadik Rrahmani, Gëzim Hasi, Besnik Kollari, Shefqer Kurti apo trajneri Hysni Maxhuni.[2]
