The club was formed in 1928 as FK Sandžak and has achieved its greatest successes since Serbia has become an independent country, reaching the top tier of national competition for the first time ever in 2011.

Novi Pazar was granted promotion after 2010–11 Serbian First League champions BASK withdrew from the SuperLiga due to limited funds and not meeting the required stadium criteria set out by the Football Association of Serbia.

The Serbian Republic League at time was very competitive and Novi Pazar that season finished top of teams such as Radnički Kragujevac, Čukarički, Obilić, Sinđelić, Jagodina, Sloga Kraljevo, Loznica, Dubočica, Radnički Obrenovac, Budućnost Valjevo, Rudar Kostolac, Kristal Zaječar, Majdanpek, Đerdap Kladovo and 7.

Juli, but the major celebration happened two rounds earlier when Novi Pazar secured the league title at the 1–1 draw away in Belgrade against Sinđelić.

The players that formed that notorious generation of Novi Pazar that season were goalkeepers Novica Jovanović, Dragan Goševac, Naser Halitović, defenders Dragan Kostić, Bajro Župić, Darko Vujović, Esad Karišik, Nazim Izberović, Ratko Šarac, Radojica Milojević, Salih Detanac, Izet Ljajić, Ljutvo Bogućanin, midfielders Ferid Ganić, Rizo Tutić, Mirsad Karišik, Adnan Numanović, Ismail Bihorac, Nermin Ukić, and forwards Ismet Ugljanin, Milan Glavčić, Gmitar Vukadinović, Šerif Izberović and Naser Salihu.

As winner of the 1983–84 Serbian Republic League, FK Novi Pazar represented Serbia that year and won the tournament.

After beating Liria away in Prizren by 3–0, Novi Pazar played the final home in the City Stadium where it won Crvenka by 2–0 with goals of Esad Karišik and Ismet Ugljanin.

During the 1980s and 1990s the club was magnet to many of the talented Kosovo Albanian players such as Nazmi Rama, Naser Salihu, Mentor Miftari, Sadik Rrahmani, Gëzim Hasi, Besnik Kollari, Shefqer Kurti, or manager Hysni Maxhuni.

Ivan Babić participated in a historic moment for FK Novi Pazar after scoring the first goal in the top division for the club.

"[6] Like most of the playing squad, Dragoljub Bekvalac had not received payment in the previous four months and promptly resigned from the position of coach, and even considered suing the club via the district court for compensation.

[8] Subsequent to the announcement of the new coach, the former leader of Partizan's medical team, dr. Sead Malićević, was named the new president of the club.

[11] The stadium began undergoing complete reconstruction during the first half of 2011 in an ambitious project by the Football Association of Serbia and the city of Novi Pazar.

The project includes also the covering of the whole stadium, new floodlights, new locker and press room, new ambulance, parking area, ticket office.

In October 2012, Ekstremi held up a mocking display about the illegal organ harvesting in Kosovo as a provocation to Rad, a team from outside of Novi Pazar from where the supporters were mostly Christian Serbs.

Torcida Sandžak, on a different note, earned worldwide recognition when the group organized a protest in the form of a public march which was attended by thousands of people.