There may have been inhabitants in Tetovo's area as early as the Bronze Age and a proof of that is the statue of bronzed dancer from the Illyrian period, 6th century BC which is the oldest archaeological finding in Tetovo region.
Tetovo was officially founded in the 14th century as a small medieval Orthodox settlement around the Sveta Bogorodica (Holy Mother of God) church. Tetovo grew with the building and construction of houses around the Orthodox Church. This was at the foothills of the Sar mountain.
At the end of the 14th century, Tetovo, along with all of Macedonia, fell under the rule of the Ottoman Empire. As the Muslim population in Macedonia began to expand in the early Ottoman period mosques, baths, and markets began to appear as early as the 15th century. Tetovo under Ottoman tutelage became an important trade center for the local farmers and craftsmen, as well as an important military fortification.
In the 15th century, Tetovo began to be regarded as a major city in the region. The Turkish writer Mehmed Beg in 1436 in the Vakuf noted that Tetovo had stores and shops and was one of the most prosperous regions in the Polog valley. In 1470, Mehmed Kebir Chelebija noted the rapid development of Tetovo. In 1565, under Ottoman Turkish rule and occupation, Tetovo was refereed to as the "episcopal religious place Htetovo", an Orthodox religious center, the seat of the Orthodox Church and domicile of the Orthodox religious leader.
Turkish influence deeply impacted Tetovo and it was renamed Kalkandelen to reinforce the new Islamic presence. Haci Halife in the 17th century noted in his writings that Kalkandelen was expanding at an amazing rate in its lowland areas. In the 18th and 19th centuries, the city began to expand greatly. Tetovo was divided into the Orthodox Slavic quarter and the Muslim Turkish quarter. The Orthodox Slavic quarter or section was on the left bank, on the Pena River, while the Turkish Muslim quarter was on the right bank.
By the 19th century, when the population of Tetovo began to increase with settlement from the surrounding villages, the French traveler Ami Bue noted that the population had reached about 4,500 people.
In 1912, due to the Balkan wars and the division of Macedonia, Tetovo became a Serbian city.
In the Second World War Tetovo was jointly ruled by Italy and its regime in Albania. Tetovo was in the Italian zone of occupation until September 3rd, 1943, when Italy surrendered and Germany re-occupied Macedonia. Ethnic Albanians in Macedonia formed the National Albanian Committee to advance the Greater Albania movement and agenda.
The Communist Party of Macedonia, was formed on March 19th, 1943 in Tetovo. Tetovo was liberated by the partisans on November 19th, 1944.