Die frühesten Spuren menschlicher Besiedlung im Raum Skopje wurden innerhalb der Festung Kale gefunden. Sie datieren aus der Jungsteinzeit und sind über 6000 Jahre alt. Die von Archäologen zu Tage gebrachte Siedlung ist von einem noch unbekannten Volk gegründet worden, das von der Jungsteinzeit bis zur Frühen Bronzezeit über einige Jahrhunderte in der Region lebte. Die ersten bekannten Siedler in der Umgebung von Skopje waren die Triballer, die zu den Thrakern gehörten. Nach ihnen kamen die Päonier, doch im 3. Jahrhundert v. Chr. konnten die Dardaner, ein illyrischer Stamm, das Gebiet besetzen und sie gründeten ein großes Königreich, das von der Scupi genannten Siedlung über Naissus im Norden bis hin zu den Albanischen Alpen im Westen reichte. Die Dardaner erklärten im 2. Jahrhundert v. Chr. Scupi zu ihrer Hauptstadt und dehnten ihr Reich bis nach Bylazora (beim heutigen Veles) im Süden aus.

Die Römer eroberten im Zuge der Makedonisch-Römischen Kriege 168 v. Chr. auch das Reich der Dardaner, doch jahrzehntelang konnten sie ihre Herrschaft in Makedonien und Illyrien nur spärlich durchsetzen. Der römische Kaiser Domitian (81 bis 96 n. Chr.) siedelte zu Beginn seiner Herrschaft Veteranen der Legionen I Italica, III Augusta, IV Macedonica, V Macedonica, V Alaudae, IIII Flavia und VII Claudia in der einem Militärlager ähnelnden Siedlung Scupi an.[10] Der Ort erlangte 86 n. Chr. den Status einer Colonia und wurde auch Colonia Flavia Aelia Scupi genannt.

Die nächsten Jahrhunderte waren für die kleine Stadt sehr wechselvoll. Im Jahr 518 zerstörte ein Erdbeben die gesamte Stadt; der oströmische Kaiser Justinian I. ließ sie jedoch wieder aufbauen. Es vergingen nicht einmal 100 Jahre, als im Winter 594/95 im Zuge der Landnahme der Slawen auf dem Balkan Stämme der Slawen die Stadt dem Erdboden gleichmachten. Das Mittelalter zwischen dem Einfall der Slawen bis zur Eroberung durch die Osmanen im 14. Jahrhundert war von blutigen Machtkämpfen zwischen regionalen Mächten, allen voran den Byzantinern und Bulgaren, geprägt. Im 9. Jahrhundert schlossen letztere die Stadt dem Ersten Bulgarischen Reich an und konnten sich für einige Jahrzehnte behaupten. Zar Roman erklärte im Jahr 980 Skopje für kurze Zeit zur bulgarischen Hauptstadt und Sitz des bulgarischen Patriarchen. Im Jahr 1004 kam es im Umland von Skopje zu einer großen Schlacht zwischen Byzantinern und Bulgaren. Nach dem Fall des Ersten Bulgarischen Reiches 1018 eroberten die Byzantiner die Stadt und erklärten sie zum Hauptort des byzantinischen Themas Bulgaria. Die Herrschaft von Byzanz währte allerdings nicht lange und führte zur Stärkung der lokalen Boljaren. Schon im 12. Jahrhundert konnten die Bulgaren, nach einem Aufstand Skopje zurückerobern und sie ihrem Zweiten Reich angliedern. Der Boljar von Skopje, Konstantin Tich Assen wurde im bulgarischen Bürgerkrieg zum bulgarischen Zar ernannt und die Region um Skopje wurde in der Folge direkt den bulgarischen Zaren unterstellt.

Im Jahr 1282 entriss der serbische Nemanjidenkönig Milutin die Stadt den Bulgaren. Skopje entwickelte sich zur neuen Residenzstadt der serbischen Herrscherdynastien. Am 19. Januar 1392 geriet Skopje für mehr als 500 Jahre unter osmanische Herrschaft. Eine für die hochosmanische Zeit (16./17. Jahrhundert) bedeutende ausführliche Beschreibung Skopjes, drei Jahrzehnte vor der Inbrandsetzung Skopjes durch den habsburgischen General Giovanni Norberto Piccolomini im Jahre 1689, findet sich im "Reisebuch" (Seyahatnâme) des osmanischen Reisenden Evliya Çelebi. Er beschrieb die Stadt als eine gewaltige Siedlung, welche sich auf beiden Seiten des Vardars erstreckte. Die Entwicklung Skopjes wurde abrupt unterbrochen, als im Großen Türkenkrieg (1683-1699) österreichische Truppen unter General Giovanni Norberto Piccolomini bis nach Mazedonien vordrangen. Am 25. Oktober 1689 nahm seine Armee die Stadt ohne große Kämpfe ein, weil die osmanische Streitmacht und viele Einwohner den Ort verlassen hatten. Piccolomini befahl, Skopje niederzubrennen, was am 26. und 27. Oktober geschah. Angeblich sollte der Ausbreitung von Cholera vorgebeugt werden. Der Brand zerstörte viele Häuser und Geschäfte. Das jüdische Viertel wurde am schlimmsten getroffen. Die meisten Wohnhäuser, zwei Synagogen und die jüdische Schule wurden vom Feuer vernichtet.

Die Stadt erholte sich nur langsam von dem Brand. Die auf diese Zerstörung im Jahre 1689 folgenden hundert Jahre der Geschichte Skopjes liegen weitgehend im Dunklen. Auch Skopje kam im 19. Jahrhundert in die Wirren des Nationalismus' auf dem Balkan. 1844 organisierten Albaner einen Aufstand gegen das Osmanische Reich. Sie protestierten gegen die ihnen auferlegten, zu hohen Steuern und der Politik der Zentralisierung. Nach der Zerschlagung des Aufstandes wurden viele albanische Einwohner nach Kleinasien inhaftiert oder verbannt.Ein Aufschwung setzte im Laufe des 19. Jahrhunderts ein, nicht zuletzt durch den vom spätosmanischen Staat vorangetriebenen Bau von Eisenbahnverbindungen, verbunden mit dem Zuzug nichtmuslimischer Bevölkerung. Ab 1873 war Skopje durch eine Eisenbahnlinie entlang des Vardar verbunden mit Thessaloniki, 1888 auch mit den serbischen Bahnstrecken. So war die Stadt von nun an über Belgrad direkt mit Mitteleuropa verbunden. Skopje war Hauptort eines Sandschaks und ab 1888 (Pristina ablösend) Hauptstadt der osmanischen Provinz (Vilâyet) Kosovo. In dieser Zeit wurde Skopje zur drittgrößten Stadt Makedoniens nach Thessaloniki und Bitola. So hatte Skopje um die Jahrhundertwende zum 20. Jahrhundert 30.000-40.000 Einwohner.

Im August 1912 wurde Skopje von 30.000 albanischen Aufständischen eingenommen, die von Isa Boletini angeführt wurden und gegen die Politik des Osmanischen Reiches vorgingen. In den Balkankriegen wurde Skopje am 25. Oktober 1912 durch die serbischen Streitkräfte erobert und geriet unter die Herrschaft von Belgrad. Die serbischen Truppen richteten ein regelrechtes Blutbad in der Stadt an. Albanische und türkische Häuser wurden in Brand gesetzt, Menschen wurden geköpft und ihre Leichen in den Straßen aufgestapelt. Laut einem Bericht von Leo Trotzki wurden nicht nur Männer, sondern auch Hunderte von Kindern und Frauen lebendig in Brand gesetzt. Durch die neue Grenzziehung nach den Balkankriegen 1912 und 1913, als Bitola zur Grenzstadt mit Griechenland wurde, begann der Aufstieg Skopjes zum unumstrittenen Zentrum "Südserbiens". Während des Ersten Weltkrieges wurde sie am 10. Oktober 1915 von bulgarischen Truppen eingenommen. Dabei zündeten die Serben bei ihrem Abzug den nördlichen Teil der Stadt an, was große Schäden an historischen Bauwerken verursachte. 1918 wurde Skopje von Serbien zurückerobert und gehörte wie auch das ganze heutige Mazedonien danach zum Königreich der Serben, Kroaten und Slowenen, das 1929 in Königreich Jugoslawien umbenannt wurde und im gleichen Jahr Skopje zur Hauptstadt der neu errichteten Vardarska banovina (Banschaft Vardar) machte. Im Zweiten Weltkrieg wurde Skopje von 1941 bis 1944 erneut von bulgarischen Soldaten und Kämpfern der VMRO besetzt und am 2. August 1944 zur Hauptstadt der neuen Sozialistischen Republik Mazedonien erklärt, die eine Teilrepublik des kommunistischen Jugoslawiens stellte.

Um 5:17 Uhr des 26. Juli 1963 ereignete sich ein schweres Erdbeben, das in die Geschichtsbücher einging. An diesem Tag bebte die Erde und die Katastrophe forderte 1070 Todesopfer. Rund 75 Prozent der Einwohner verloren ihr Obdach und 3300 Personen erlitten schwere Verletzungen. Nahezu die ganze Altstadt wurde dem Erdboden gleichgemacht. Die Erschütterungen konnten über das ganze Land und auch im angrenzenden Kosovo und Serbien gespürt werden. Insgesamt entstand ein Sachschaden von über einer Milliarde US-Dollar. Mit internationaler Hilfe wurde Skopje in den nächsten Jahren wiederaufgebaut; der japanische Architekt Kenzo Tange entwickelte für die Stadt am Vardar einen Masterplan. Seit 1991 ist Skopje die Hauptstadt der unabhängigen Republik Mazedonien. Während des Kosovokriegs nahmen die Stadtbehörden Tausende von Flüchtlingen aus dem benachbarten Kosovo auf. Nur einige Kilometer nordöstlich von Skopje bei Aracinovo fanden während des albanischen Aufstands 2001 blutige Kämpfe zwischen der mazedonischen UÇK und der staatlichen Polizei statt.