The team was established in 1954 under name KK Mavrovo. It changed its name numerous times over the year. KK Goteks, KK Vardar-Komerc, KK Gostivar and KK Nikol-Fert Gostivar. KK Gostivar [1] is three times republic league champion of Macedonia. In the golden age of its existence it won three title in: 1965, 1967 and 1968. They waited for a long time for their fourth title but after 32 years they won their 4th title in 2000. Next year in the season 2000-01 they won their first Macedonian Basketball Cup by beating KK Rabotnički in the final 72–65. Next season they once again defeated Rabotnički 88–82 to claim back to back Cup titles.
They played 4 times in European competition. In the season 1996/97, 1999/00 and 2000/01 they played in FKC/FIBA Korac Cup. In the 2002/03 season they played in FRC/FIBA-Europe Regional Challenge.