I oldtiden var det meste af nuværende Makedonien en del af Kongeriget Paeonia, der var befolket af det oprindelige thraciske folk. Men mindre dele var dog underlagt det gamle Illyrien samt Dardanien. Det var et rige uden faste grænser, og år 336 f.Kr. begyndte en brydningstid, der senere endte med, at den berømte Alexander den Store overtog hele området frem til Donau. Romerne opfattede dog dette som deres, og den nordlige del af området blev derfor delt mellem Makedonien og Moesia prima.

Senere kom de slaviske folkeslag til Balkan, og bosatte sig i regionen. Makedonien konverterede til kristendommen omkring 9. årh. under den slaviske prins Boris I af Bulgarien. År 1.014, blev kejser Basil II besejret af Zar Samuil af Bulgarien, og år 1.018 mistede byzantinerne kontrollen over Makedonien og i øvrigt hele Balkan, som de havde styret siden år 600.

I det 13. årh. blev det bulgarske imperium genoplivet med kontrol over området. Dog havde imperiet politiske vanskeligheder, og regionen kom igen under byzantinsk kontrol omkring år 1.400. Og det var dog i denne periode, man mistede området til det serbiske imperie, der anså sig selv som befriere fra det byzantinsk despoti. Herunder blev Skopje hovedstad i Tsar Stefan Dusan's imperium. Ved Dusan død startede igen en magtkampe mellem adelen om magten over Balkan. Og det faldt uheldigvis sammen med, at Osmannerne var kommet til Europa. Og da det serbiske imperium faldt til osmannerne i det berømte slag på Solsortesletten, var der ikke mere nogen til at forsvare kristendommen på Balkan, hvorefter osmannerne fik det hele, som de beholdt i næsten 500 år.