The club was founded in 2012 after the merger of FC Albarsa and FK Sloga Jugomagnat. The club is the successor and phoenix club of FK Sloga Jugomagnat. On the initiative of fans in 2006 and in cooperation with sports workers, former players, local populations, NGOs, and with the help of the Mayor in 2013 the club eventually honors its name to FC Shkupi.
Shkupi's biggest rival is FK Vardar. During the 1990s, the city derby was one of the biggest in the league, until financial troubles plagued the club and was relegated to the second league. In the second league, Shkupi developed a rivalry with FK Teteks as Tetek's supporters have a connection with Vardar supporters.