The first fortress was built in 6th century AD on a land that was inhabited during the Neolithic and Bronze Ages (roughly 4000 BC onwards). It was constructed with yellow limestone and travertine, along with fragments of Latin inscriptions. Material for the fortress originated from the Roman city of Skupi, which was completely destroyed by an earthquake in 518.

The fortress is thought to have been built during the rule of emperor Justinian I and constructed further during the 10th and 11th centuries over the remains of emperor Justinian's Byzantine fortress which may have been destroyed due to a number of wars and battles in the region. The city was capital of the First Bulgarian Empire between 992 and 1015, and was center of the uprising of the Bulgarian Empire against the Byzantine Empire under the rule of Peter Delyan. Not much is known about the Medieval fortress apart from a few documents which outline minor characteristics in the fortress' appearance.

In 1346 at the Skopje Fortress, Stefan Dušan adopted the title of Emperor at his coronation and he had transferred the capital of Serbian Empire to Skopje.^[3][4][5]

In 1660, Evliya Çelebi, a chronicler of the Ottoman Empire, wrote an in-depth account on the appearance of the fortress while traveling through the territories of the Empire:

It is a fortified city, a very strong and sturdy fortress with double walls. The city gate and the walls are built from chipped stone that shines as if it were polished. One can not see so much refinement and art in the construction of any other city. The city lies in the middle of Skopje. It is a tall city, of a shedadovska construction and five-sided shape. The walls, that surround the city from all sides, reach the height of around fifty arshini. The city is protected by seventy bastions and three demir gates on its southeast side, and there are many guards in the entrance hall. The door and walls of the entrance hall are decorated with different arms and tools needed for the arms. There is no site or location that can dominate the city. It lies on tall rocks, so that one can see the whole plain. The river Vardar flows on its western side. On the same side of the city, there is a road that leads through the caves towards the water tower located at the riverbank. Since there is an abyss at this side of the city, as scary as the depths of hell, there are no trenches, nor there can be one. On the east, southeast and north side of the city, there are deep trenches. On that side, in front of the gate, there is a wooden bridge that lies over the trench. The guards used to lift the bridge using a windlass, which provided for defense of the gate. Above the gate, there is an inscription, giving more information about the reparations of the gate that took place in the past. The inscription reads: The wise son of Mehmed-han in the year 1446.

The fortress was partially destroyed yet again by an earthquake in 1963 but was not reconstructed until recently.^[6][when?]

In late 2006 and early 2007, research and excavation of the Skopje Fortress funded by the Macedonian government had finally commenced. Researchers discovered woodwind instruments and clay ornaments dating as far back as 3000 BC. Excavation of the main fortress also revealed houses below the fortress' visible level. The discoveries are believed to have belonged to inhabitants of Scupi on which the fortress was built. Archaeological excavations continued in 2009.^[7]

In May 2010, archeologists unearthed the largest stash of Byzantine coins ever found in Macedonia at the fortress.^[8]

After the foundations of a 13th-century church were found within the complex, the Cultural Heritage Protection Office actioned a project to restore it in the form of a church museum. Ethnic Albanian groups, with DUI at the forefront, claimed the site contained an older Illyrian structure, and that by virtue of their claimed Illyrian ancestry, the site should be theirs.^[9] The dispute revolved around competing claims to the area as being either Christian or Muslim and Macedonian or Albanian.^[10]

On February 10, 2011, late at night, a crowd of about 100 ethnic Albanians converged on the site to find over 50 construction workers from Bitola working on the steel church museum.^[11] When questioned who ordered the construction the workers refused to answer but revealed that they were instructed to start building from 10:00 PM over the night.^[11][12] Some of the crowd proceeded to destroy and vandalize parts of the scaffolding, the same day restoration was resumed after it was officially halted by the government.^[11][13] The construction workers were removed from the building site by the Macedonian police.^[11][12] According to media footage, high-ranking ethnic Albanian ministers and members of DUI leadership were among the crowd.^[14] Two weeks prior to the event, DUI spokespeople had demanded the termination of the project.^[14] During the next two days, Macedonians on Facebook called on each other to converge on the site and protect the site and its workers. Members of both groups arrived almost simultaneously on February 13 and a violent clash erupted, leaving around 10 injured, including 2 policemen.^[10][15][16]

The opposition, Macedonian and Albanian, condemned the violence, criticized the prime minister Nikola Gruevski for creating inter-ethnic tensions and called on the government to take responsibility for it. The Social Democratic Union of Macedonia, the most numerous opposition party, claimed that this event was staged as an attempt to distract the people of Macedonia from the reigning poverty and corruption. The Albanian New Democracy also reacted that "they should not destroy the future of the country by focusing on its past".^[17] The Turkish Ministry of Foreign Affairs reacted:

"The decision of the Government of Macedonia to construct a church-museum on the Skopje Fortress on its most visible spot is going to create serious tensions in the society. Turkey pays special attention to preserving and protecting the cultural heritage that is left in Macedonia from the Ottoman Empire."^[18]

Various political analysts claimed that the incident was orchestrated by the Macedonian and Albanian governing parties, namely VMRO-DPMNE and the Democratic Union for Integration.^[19] Vllado Dimovski, head of the "Center for inter-ethnic tolerance" in Macedonia, stated that "the coalition partners (VMRO-DPMNE and DUI) orchestrated the violent event on the Skopje Fortress to distract the public from the problems that the country is facing".^[19]

•  
  Tower at Kale Fortress
•  
  Minaret of Mustafa Pasha Mosque from Kale Fortress
•  
  Statue at the fortress
•  
  View of the Skopje Fortress (right-center) from Vodno
•  
  Ruins inside the fortress
•  
  Skopje Fortress in the early 1920s
•  
  Front side of the fortress
•  
  View of the wall from the interior
•  
  Night view of a tower
•  
  Historical images of Skopje: view of Kale
•  
  Plan of the medieval fortress Skopje
•  
  A view of Stone Bridge and Skopje Fortress, Skopje

• List of castles in North Macedonia

• Official site dedicated to the Skopje Fortress