 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, the Municipal League, KF Shkëndija played their first match against FK Kosmos, winning 4-0.Shkëndija won the division in the 1979–1980 season, resulting in Shkëndija being promoted into the Third division.