In 1946 there was a club from Tetovo called Šar Tetovo,and it competed in the Macedonian Republic League and Macedonian Cup.It won the Macedonian Cup two times in 1948 and 1950 and was successful in the Macedonian League. However, it was dissolved after a few years, mostly because of financial difficulties. Not much long after this, a new club was founded on the base of FK Šar, named Tekstilec.
The club was founded in 1953 under the name FK Tekstilec. The founder of FK Teteks is the textile combine Teteks and because of this they are known as "Štofari" (Tailors). They were in the shadow of the older club FK Ljuboten (formed in 1919). FK Ljuboten's squad was full with home grown players from Tetovo, while Teteks had the capability to attract the best players from Macedonia and wider from the former SFR Yugoslavia. They won the Macedonian Republic League on four occasions and along with Vardar, was the only other Macedonian club to have won the Federal EasternYugoslav Second League containing teams from 3 federal Republics: Macedonia, Montenegro and Serbia.
Teteks played in the inaugural Macedonian First League, but finished 17th and were relegated. The club was bought by a German concern UFA Media Group with Braco Vujčić as chairman. After winning the Macedonian Second League in 2009, they were promoted back to the top level of Macedonian football, for the 2009/2010 season. Teteks claimed their first Macedonian Football Cup in 2010 and in the summer made their European debut in the UEFA Europa League. In 2013, Teteks made history by becoming the first relegated team in Macedonia to win the national Cup.
Derby of Tetovo – Tetovo's big derby match used to take place between FK Teteks, whose fans are working class, and FK Ljuboten, whose fans are the oldest citizens of Tetovo. But today's main rival of FK Teteks is FK Shkëndija, whose fans are predominantly of Albanian descent.
The supporters of FK Teteks are named Vojvodi (Dukes) since 28 October 1988. They are also known as Vojvodi Jug (South Dukes) because their home side tribune is on the south side. The Vojvodi's well-known motto is "Со Верба Во Бог – Војводи До Гроб" (With trust in God, Dukes till the grave). They have a great relations with FK Vardar fans, Komiti Skopje.