Bereits im 4./5. Jahrhundert fielen Hunnen und Goten in Makedonien ein, ließen sich dort jedoch nicht nieder. Seit dem 6./7. Jahrhundert besiedelten Slawen den Balkan, darunter auch Makedonien und große Teile Griechenlands.[1] Dadurch kam es zu tiefgreifenden ethnischen Änderungen: Die Slawen vermengten sich mit der ortsansässigen Bevölkerung, die sich aus Paionen (protobulgarische Stämme aus Paionien unter der Führung von Kuber[2]), antiken Makedonen und anderen ethnischen Elementen zusammensetzte. Bereits im 7. Jahrhundert war Makedonien offenbar so sehr slawisch geprägt, dass es in byzantinischen Quellen auch als Sklavinia (Σκλαυινία) bezeichnet wurde.[3] Allerdings blieb in den Städten die byzantinische Kultur nach wie vor lange erhalten. Im byzantinischen Reich wurden die Slawen zu einem bedeutenden Faktor und sicherten sich ausgedehnte Siedlungsräume überwiegend im Kernland des geographischen Makedoniens und Thrakiens und drängten die hellenisierte Bevölkerung bis auf ein paar Inseln im Binnenland immer mehr an die Küsten.
Im 9. Jahrhundert geriet der größte Teil der Region Makedonien unter die Herrschaft des ersten bulgarischen Reiches mit dem Herrscher Krum Khan. 811 verlor das byzantinische Reich die Schlacht von Pliska gegen das erste bulgarische Reich. Zwei Jahre später, 813, wiederholte sich die byzantinische Niederlage gegen das erste bulgarische Reich in der Schlacht von Adrianopel. Der byzantinische Machtbereich schrumpfte nachfolgend zugunsten des bulgarischen zusammen; vor allem Thrakien und Makedonien kamen unter die Kontrolle des bulgarischen Reiches mit seinen Herrschern Presian I. (836–852), Boris I. (852-889), Simeon I. (893-927) und Peter I. (927-969). Um diese Zeit fand eine Christianisierung der Bevölkerung statt, sowie die Verbreitung von slawischer Literatur, die in glagolitischer und kyrillischer Schrift verfasst wurde.[4] Nach dem Tod von Zar Peter 969 zeigte das erste bulgarische Reich Zerfallserscheinungen. Das byzantinische Reich unter Kaiser Basileios II. (bulgarisch Wasilij II.) Bulgarroktonos (der „Bulgarentöter“) konnte in der Schlacht von Kleidion am 29. Juli 1014 die Bulgaren unter Zar Samuil besiegen.
Nachfolgend wurde die Region Makedonien in das Byzantinische Reich eingegliedert. 1185 unternahmen Normannen eine Belagerung von Thessaloniki, nachdem sie aus Italien angekommen an der heutigen albanischen Küste bei Durres gelandet waren. 1204 fiel im vierten Kreuzzug die byzantinische Hauptstadt Konstantinopel (heute Istanbul) an die Kreuzfahrer, welche nachfolgend Kreuzfahrerstaaten errichteten. Die südlichen Teile der geographischen Region wurden dabei unter die Kontrolle des Königreich Thessaloniki mit seinem König Bonifatius von Montferrat gestellt. Direkt nach der Etablierung der lateinischen Kaiser- und Königreiche kam es zu bewaffneten Auseinandersetzungen zwischen den lateinischen Staaten und dem Bulgarischen Reich. 1205 unterlag das Lateinische Kaiserreich von Byzanz den Bulgaren unter Zar Kalojan in der Schlacht von Adrianopel und verlor seinen Kaiser Balduin in bulgarischer Gefangenschaft.
Dem zweiten bulgarischen Reich gelang damit die Etablierung einer Kontrolle über weite Teile insbesondere des Norden der Region Makedonien (und Thrakien). 1207 starb der König von Thessaloniki Bonifatius von Montferrat in einem Gefecht mit bulgarischen Truppen; im gleichen Jahr verstarb der bulgarische Zar Kalojan bei der Belagerung von Thessaloniki. Nachfolgend schrumpfte das Herrschaftsgebiet des Königreichs Thessaloniki in Norden und Nordosten unter Druck des bulgarischen Reiches sowie im Südwesten und Westen durch Druck des Despotats Epirus. 1224 wurde der südliche Teil Makedoniens durch das Despotat Epirus mit der Einnahme der Stadt Thessaloniki erobert. Das expandierende Despotat Epirus geriet darauf hin in Konflikt mit dem ebenfalls expandierenden bulgarischen Reich.
Mit der für die Bulgaren und das zweite bulgarische Reich unter Zar Iwan Asen II. siegreichen Schlacht von Klokotniza 1230 wurde geographische Region Makedonien unter die Kontrolle des zweiten bulgarischen Reiches gestellt. 1259 fielen mit der Schlacht von Pelagonien die südlichen Anteile der geographischen Region Makedonien wieder an das byzantinische Reich. 1321 brach im byzantinischen Reich ein Bürgerkrieg aus, welcher auch den Süden der geographischen Region Makedonien betraf. Im Zuge dieses Bürgerkriegs wurden landwirtschaftliche Betriebe und Besitzungen zerstört.[5] 1330 führte der bulgarische Herrscher Michael Sisman einen Feldzug gegen Nordostmakedonien, welcher gegen den serbischen König gerichtet war.[5] Die bereits im byzantinischen Bürgerkrieg sichtbar gewordenen Unruhen setzten sich mit Aufständen in den Städten Makedoniens fort. Der prominenteste dieser Aufstände war die Zeloten-Herrschaft in Thessaloniki von 1342 bis 1349, welcher zur weitgehenden Entmachtung des byzantinischen Adels und Klerus in Thessaloniki führte.[5]
Mitte des 14. Jahrhunderts bis 1355 eroberte das serbische Königreich unter Stefan Uroš IV. Dušan die gesamte Region Makedonien mit Ausnahme von Thessaloniki und seiner unmittelbaren Umgebung und darüber hinaus weite Teile des griechischen Festlandes. Nach dessen Tod 1355 konnte sich die serbische Kontrolle nicht halten und die Gebiete einschließlich der Region Makedonien gelangten für kurze Zeit unter erneute byzantinische Herrschaft.
