The following settlement remains belong to the Middle Ages city. At the present stage of research there is an open dilemma as regards the possible connection of the monumental, so-called cyclopic wall to the major building activities in the vicinity of Skopje during the great tzar Justinian or in the VI century. This wall, built from great stone blocks, coated from within with strong mortar and 2.80-4.20 m wide, represents a unique building-work sample on the Balkans. Nevertheless, without further research of individual indicative positions in order to resolve this question, such as is the position on the eastern terrace, we are left to merely presume the precise time of the initial erection of the monumental wall, as well as the actual role and significance of the Kale in the time of Justinian.
The researched points on the Kale have not revealed settlements or more evident cultural manifestations from the VI century so far. However, certain ceramic finds or the several coins leave it open for further research in this direction and the discovery of more remains from the possible settlement dated from the time of Justinian.

Even so, the uninterrupted and turbulent historic development into a real urban centre or Medieval Skopje begins somewhere towards the end of the X century or in the time of Samuil and persists nowadays.
At that time, under the rule of Samuil, the Skopje Kale was protected by solidly built walls, which completely surround the Upper city, forming, in many respects, a unique fortification system, built according to the highest criteria and building techniques at the time. The numerous discovered coins dated from between the X and XI century, the burials immediately on the internal side of the southern wall, war hatchets and arrows, ceramics and other smaller finds from the same period also imply that the Kael at the time was probably a great military stronghold. The fortress was strategically set into the centre of Samuil’s state, where from it kept contact with Prilep, Bitola, Prespa, Ohrid and other cities in the south, with Prizren and the Adriatic cities in the west, with Belgrade and Vidin in the north and with Sredetz (Sofia) in the east.
On the researched points, in sectors 4 and 5, along the southern wall, remains were found of numerous wooden constructions with waste pits, hearths, kilns and remains of metalwork. Most of these were most probably barracks for the soldiers, warehouses, blacksmiths’ workshops for weapon making and repairing, all in some sort of relation to the wall from the interior.
In Sector 5, for the same city, a southern entrance to the fortress was revealed with all the associated elements, which would be used and renewed on several occasions in the following centuries as a main entrance both to the  later medieval and to the early Ottoman fortress.
In continuation of the entrance section to the east, remains were found from a cobblestone surface - road which led along the internal part of the southern wall to the higher parts of the terrain. The discovered ecclesiastic, stone decorations in this part of the terrain point out that somewhere in this parts (in the still unexplored sections), in the X-XI century, there was at least one church.
All remains from this, hypothetically speaking, "Samuil’s" phase are supported by coin finds of so-called anonymous folles, as well as of the emperors Basil II, Nikephoros III and Michael VII,  all dated from the X and XI century,  mostly discovered in their original position. 
All of this neatly documents the notable place and the great historical, economic and political significance of the Skopje Fortress during the age of tzar Samuil and his successors. 

Towards the end of the XI century (from 1081-88 and again in 1097) Skopje is held by the Normans (Vikings) who previously occupied the Byzantine southern Italy from whence they spread across the Balkans. Accordingly, general Puntesy with 200 hoplites took over first of all the cities in present day’s Southern Albania and through Ohrid and Polog arrived in Skopje, which was in their hands from 1081 until 1088. The Normans were known producers of high-quality weapons made of good steel.
Parts of workshops and blacksmiths dated from this period have been found near the south-eastern tower of the Kale, in Sector 10, with iron and chrome slag, as well as parts of a Viking crossbow. This was a fierce weapon in Europe of that day and it was used only by the Vikings, hence the find from the Skopje Fortress is the best confirmation of the presence of the Normans in Skopje.

During the rule of the Komnenos dynasty throughout the entire XII century, peace and wellbeing ruled in the Byzantine Empire. Based on the finds of stone pieces from iconostasis decorations at least 2 churches were erected on the Skopje Fortress at that time. The other finds in the layers from the XII and XIII century illustrate Skopje as a real centre, and economic focus of the wider Balkan region.
At the Skopje Fortress there are numerous coins from the Komnenos, Angelos and Doukas dynasties and in a proportion correlating to the economic and political circumstances in the empire.
During this period the kale was home and workplace to several metalwork craftsmen whose workshops are scattered along the city walls. Just as important, if not more so, is the work of numerous potters. Besides the daily kitchen and storing ceramics, their top products were the luxurious dining dishes decorated by painting, engraving and glazing. Some of the plates found are real works of art, and the entire collection of this ceramic is one of the most numerous and most valuable on the Balkans. All of these products were exported throughout the wider mid-Balkan region.

Based on the historical sources from 1204-1264 this is when the Byzantine Empire was crushed and divided into several smaller states for the first time. Skopje is fought for by: Bulgarians, Serbians, Epirean, the feudal lords from Prosek and Thessalonica, the tzars from Nicene. The economic fall of the empire is reflected in the quality of the money and the other products. However life in Skopje’s Upper City continued with undiminished intensity, whereupon it is good to remark that Lower City  was fortified by walls.
Besides the presence of money from these newly created principalities, the Skopje Fortress holds as well coins of the medieval Bulgarian state of Ivan II Asen (1218-1241) and of Serbia of Stefan Urosh II Milutin (1282-1321). Nevertheless of all newly created political entities the most frequent are the coins of the Palaiologos dynasty, and by far the most present are the ones of Michael VIII (1259-1282).

            The historical data imply that from end of the XIII until the end of the XIV century Skopje was held by the Serbians. The Serbian administration came In the stead of the Byzantine clerks, and king Stefan Dushan moved the seat of the throne from Prizren to Skopje, where he was crowned tzar and issued the famous Code. The written sources inform us that the Upper City (Kale) was with densely set buildings and there were at least 4 churches. The results from our research abundantly documented this image. 
The city walls of the Kale bile renewed and they surrounded a completely new urban area which slightly expanded the city in the north-western section. The southern entrance gate used the old passage, but the threshold was erected for about 1 m higher, and on the eastern side a great square tower was constructed in response to the western tower. Remains from spacious public building made of stone, or of stone and brick, and techniques common for that age have been discovered at several of the examined points – in Sectors 1, 4, 5 and 10.
The highest and most dominant section of the Kale, in the south-eastern part of the city, or in Sector 3, a church has been discovered with a cross-like interior and with a necropolis surrounding it. Among other things, some of the preserved items include pieces from frescos (with stylistic-artistic characteristics from the end of the XIII-XIV century), a silver-coated chalice hidden in the crypt north of the church and a gold-coated silver vessel decorated with almandine, enamel and large Greek inscription around it (found earlier, in the southern base of the church). Bronze and silver jewellery was found in the tombs around the church, as well as numerous coins dated from the XIII and XIV century, as well as a secondary tombstone belonging to some nobleman Vlatko, with old-Slavonic inscription, dating from 1281.
Within the frames of the Skopje Fortress, based on the written sources, there were other churches as well. With the exploration of the area near the southern city wall, not far from the southern gate numerous pieces of wall-frescos from another church were dug out, as well as individual finds of crosses. In the same area (Sector 9) were most of the finds of leaden seals which implies the past existence of an ecclesiastical administrative centre somewhere in the vicinity, in the yet to be researched areas of the terrain.
From the discovered coins dated from this time several samples are of Stefan Urosh II Milutin (1282-1321) and Stefan Dushan (1331-1355). The period of the late XIV and XV century, being a period of the so-called autonomous medieval rulers in Macedonia is manifested only through one coin of king Volkashin (1365-1371).