Fragmented archaeological excavations, carried out recently, have shown that the earliest buildings, i.e., wooden and earthen huts in the Fort Kale originate from the transitional period between the Neolith and the Bronze Age. They marked the beginnings of a larger prehistoric settlement.

Although there are no excavated artifacts dating from the different phases of the Iron Age, the presumption is that the settlement could not have stayed aside from the overall changes within the region, where significant remnants of the material culture were discovered. These artifact are the evidence of rapid development of the economy, crafts, and arts, thus also of the spiritual life of the people who had lived within the region. According to the stratigraphy of the cultural layers, with longer and shorter interruptions in the continuity, the settlement within the Fort Kale hill survived, transforming gradually as a fortified strategic position on the one, and as a settlement with urban features, on the other hand.

The research showed that, under the ramparts of the present medieval fortress, there are ruins of an earlier one. It is dated back to the period between the close of the Bronze Age and the emergence of the Iron Age. According to a different opinion, the earlier fortress originates from the period when the Dardans were preparing for defending the territory from the aspirations of Rome.

Nevertheless, the fact is that in the disastrous 518 A.D. earthquake, according to the records of the chronicler Comes Marcellinus, 24 fortified settlements were devastated, including the ancient town of Skupi. Since Fort Kale is located in the immediate vicinity of the town of Skupi (at around 5 km distance), the assumption is that also the buildings that used to be within the fort were ruined. Later, with the efforts of the survived inhabitants of Skupi, Fort Kale was selected as a location of their new settlement. Certainly, they adapted and restored the ruins of the old fortress and commenced the construction of their new town at its foothill.

The latest excavations have revealed that the present medieval fortress was built during the time of the Macedonian Tzar Samuel, when it became an important defensive element of the Macedonian state against the Roman attacks. That suggests that the fortress was built within the period of the close of the X and the earliest years of the XI century.

Today visitors first notice the 121 metres long remnants of the former rampart, made up of large chiseled stone blocks. it was proved that this building material was brought from the ruined theatre of the classical town of Skupi.

Over the long centuries of its existence, the fortress, as one of rather significant strategic positions in this part of the Balkans, was frequently attacked, seized, devastated, and restored.

Later, with the emergence of firearms, it was gradually adapted to the new circumstances (sentry boxes and platforms for cannons were constructed).

Evlia Celebia, the Turkish travels-writer, who visited the fort Kale in Skopje in 1660/61, gives a more detailed description of it. He says: "It is a fortified town, with a strong and potent fort with double ramparts. The town's gate and ramparts are built of chiseled stone that shines as though it was polished. No other town has such profound and skillful construction technique. The town lies in the centre of Skopje. It is a high town and contains "sedad" buildings (low, with serrated roofs), pentagonal in shape. Encircling the town from all sides, the rampart reaches the height of up to fifty "arsini" (ells). The town is surrounded by seventy bastions and has three "demir" (iron) gates on the south-eastern side, and on the gateway of each of the high gates many guards stand. The gates and the walls of these gateways are enriched with various weapons and tools needed for them. There is no position that the town does not dominate - it itself lies on high rocks, overseeing the entire plane.

On its west side the Vardar river flows. There is a path there that leads through the caves to the "water tower" at the river bank. Also, on that side is an abyss, dire as the depths of the Hell; it neither has nor can have an exit. On the eastern, south-eastern, and northern sides, there are deep trenches. The gate is entered by a wooden drawbridge above the trench. The guards sometimes take the bridge up by a capstan, creating an additional protection of the gate. There is an inscription above the gate about its reconstruction. It says that it was reconstructed in 1446 by the son of Mehmed-han."

In such state the fortress was also found by the Austrian Commander Picolomini in 1689, as can be seen from his letter to Emperor Leopold: "The fortress was built in the old way, now completely without defense and water, there is no room for cavalry."

Travels-writers who visited the fortress in the XIX century said that is served as a store and a powder store, an army hospital, and a prison.

The compounds of the old Skopje Fort Kale were used until recently by the military authorities.

The disastrous 1963 earthquake caused great damage to the fortified town. After the catastrophe, broad conservatory and restoration activities on its ramparts were undertaken.