KF Shkëndija was formed in August 27, 1979 by Albanians from Tetovo. The purpose of forming the club was so that the Albanians throughout Yugoslavia could unite in supporting a club for Albanians. FK Shkëndija was frowned upon by Yugoslav officials as it was thought the club would awaken nationalist feeling among the Albanians of Yugoslavia. Starting at the lowest division in Yugoslavia, Shkëndija won the league in the 1979–1980 season, resulting in Shkëndija being promoted into the Third division. After claiming the third division title in the 1980–1981 season, Shkëndija was then again promoted into the Second division. However, as the popularity of the club began to increase among the Albanian population of Yugoslavia, the ruling communist government members disbanded the club, worried that the club would start a nationalistic revival in Yugoslavia.
After Macedonia declared independence from Yugoslavia, FK Shkëndija was re-established into the Macedonian Football League. It started at the Fourth division, eventually being promoted each season to the third, second and finally, to the First division. In the 2010–11 season of the First Macedonian Football League the club won its first major championship with an unbeaten run of 16 games. On 20 May 2012, Shkëndija handed FK Vardar its first loss of the season with a 1–0 victory.
During the 2012–13 season, Shkëndija was embroiled in financial difficulties and as a result, many of its players left the club earlier in the summer. The Shkëndija supporters, the Ballistët, began a social media campaign requesting Ecolog to take over Shkëndija. Albanian international, Lorik Cana and Swiss international, Xherdan Shaqiri also joined the campaign with the supporters. On 31 July 2013, Lazim Destani, father of Ecolog founder and chairman, Nazif Destani, announced Ecolog International will take charge of Shkëndija. Under the new administration, Shkëndija bought in over five new players to the squad, four days before the transfer season ended, as well as balancing the financial state of the club. The new season started averagely for Shkëndija, amassing five draws in a row. However, on 21 September 2013, Shkëndija comfortably defeated rivals FK Vardar in a 3–1 home game during the derby, displaying improvement of the club under Ecolog. However, for the next eight fixtures, Shkëndija were very inconsistent, drawing once, winning three and losing four. After losing 5–0 to FK Rabotnički, manager Gjore Jovanovski was relieved of his duties. Shpëtim Duro was named the manager Shkëndija just 15 hours after the sacking of Jovanovski. He was first hired as a temporary caretaker manager for the club's the remaining 3 games before the long winter break, but signed a contract with the club to be the manager for the remainder of the 2013–14 season.
During the winter break, Shkëndija was the most active team in the Prva Liga during the transfer period, bringing in 9 new players, further revamping the football club in preparation for the second half of the season. The second half of the season saw drastic improvement for Shkëndija under Shpëtim Duro, moving them from 8th position near the relegation zone, to 4th position at the end of the season, winning their final seven games in a row. Shkendija earned a spot in the 2014–15 first qualifying round of the UEFA Europa League.
The supporters of Shkëndija are called the Ballistët, named after the World War IIBalli Kombëtar. When the club was formed in 1979, use of nationalism was strictly prohibited by the Yugoslavian government. The supporting firm of Shkëndija called themselves BAL, using the first three letters of Balli Kombëtar. When Shkëndija was reinstated into the Macedonian Football League, the supporting firm was re-established as the Ballistët. When kick-off commences, The Ballistët always sing the national anthem of Albania.
Fans of opposing clubs barely go to Gradski Stadium as the "Ballistet" are one of the largest firms in Macedonia. This was noted when FK Rabotnički played Shkëndija in 2008. Rabotnicki had the lead over Shkëndija in Tetovo with the score 0:1. A loss would have meant relegation into the second division. At half time, Rabotnicki's players and coaches where attacked when they were leaving the pitch. Rabotnicki supporters and police could not stop the large presence of Shkëndija supporters, resulting in the match to be abandoned and Shkëndija being relegated to the second league.
On 11 September 2011, the Shkendija supporters attacked fans and players of FK Ohrid at half time. This resulted in Shkendija supporters being suspended for two home matches.
In Tetovo, the group has been responsible for the desecration of the monument to the fallen partisans in the national-liberation struggle. They graffiti "Ballistet Shkëndija" and "1992 Ultras". This occurred ten days after the Macedonian independence day.
After Partizan Belgrade defeated Shkëndija in Skopje for the qualifying rounds of the 2011–12 UEFA Champions League, Partizan coach Aleksandar Stanojevic stated that Shkëndija out played Partizan in the first half due to the great atmosphere of the Shkëndija supporters intimidating the Partizan players. In the match, the Albanian flag covered the entire west end of the stadium, along with banners such as "Ballistet", "1st state Albania, 2nd state Kosova, 3rd state coming soon" and "24 March 1999". The Ballistet chanted notable remarks such as, "Ubi ubi srbina" (Kill the Serbs) ,Adem Jashari, UÇK, Republic of Kosovo and singing Albanian nationalist songs.
On 10 March 2012, two Shkëndija supporters were arrested after a policeman was stabbed while apparently protecting two men from a mob attack. The cause of this was retaliation for the killing of two ethnic Albanians by an off-duty police officer in the town of Gostivar. After the arrests, hardcore Shkendija fans, the Ballistët, threatened to cause trouble in a match against league leaders Vardar Skopje originally scheduled for Wednesday, which had been suspended and played on another date with no fans being allowed to attend.
On May 2012, a delegation of the Ballistët ultras travelled to neighbouring Kosovo to pay their respects at a shrine to Adem Jashari, one of the founders of the Kosovo Liberation Army. On the 4 May 2012, the Ballistët joined counter-protests in ethnic Albanian neighbourhoods for the inter-ethnic violence.
On 23 May 2013, the Macedonian Cup final was abandoned late on Wednesday between Shkëndija and Teteks. The match was abandoned after 20 minutes for fear that the chants might ignite violence. The Shkëndija supporters booed the Macedonian national anthem, threw flares at the police and security as well as chanting "Ballisti Zakon", "UÇK" and other nationalistic rhetoric. Also and Macedonian fans of Teteks did the same against Albanians. The match between Teteks and Shkëndija was rescheduled for Sunday and the Macedonian Football Federation said it would be played in an empty stadium to avoid provocation.
On 19 October 2014, during the rivalry match against FK Vardar, The Ballistët held a large banner stating "They are cancer of Europe - UEFA do you need more?!" accompanied with a montage of pictures showing Serb hooligans involved in the Serbia vs England U-21 match, Italy vs Serbia match and the Serbia vs Albania match. The Ballistët are part of the TKZ ultras group that supports Albania in international football. In the next home game against FK Metalurg, the Ballistët, dissatisfied with the UEFA ruling of the cancelled Serbia vs Albania match, held banners stating "Dear Platinovic, They beat our players and won 3:0! We kill them in the return match and we get EURO 16 final spot??" along with chants against UEFA and Michel Platini.
Being a club with a strong Albanian nationalist background, Shkëndija has rivalry with most of the Macedonian football clubs. However, the biggest rivalry are with FK Vardar and FK Teteks. The Shkëndija-Teteks rivalry is one of the biggest and most heated in Macedonia. When Shkëndija play against Teteks, majority of the Tetovo police are stationed at Gradski Stadium and ban Shkendija supporters from attending Vardar-Shkendija matches in Skopje, but despite this ban Ballistet attended at Skopje two times.