De club werd in 1951 opgericht. Teteks werd enkele malen kampioen van Macedonië (1965, 1969, 1974, en 1985), de competitie was toen echter nog een onderdeel van de Joegoslavische competitie en stond gelijk aan de 3de klasse. De winnaar speelde een play-off om naar de 2de klasse te promoveren. In 1980 promoveerde de club naar de hoogste klasse van Joegoslavië. Na één seizoen moest de club echter weer degraderen nadat de voorlaatste plaats behaald werd.
Na de onafhankelijkheid van Noord-Macedonië was de club medeoprichter van de hoogste klasse maar na het eerste seizoen moest de club al een stap terugzetten en degradeerde. In de 2de klasse werd verschillende malen de 3de plaats behaald maar een promotie naar de hoogste divisie zat er niet meer in. Van 2003 tot 2005 eindigde de club nog in de top 5 maar in 2006 werd de club 10e op 12 clubs en moest een barrage spelen om in de 2de klasse te blijven en won die.
Vanaf 2009 speelde de club in de hoogste afdeling tot ze in 2013 degradeerde naar de Vtora Liga. Dat seizoen werd wel de beker gewonnen. De club keerde in het seizoen 2014/15 voor één seizoen terug op het hoogste niveau.
Aleksandar Zakoski
· 
· 