הפרובינקיה הרומית של מקדוניה נוסדה באופן רשמי בשנת 146 לפנה"ס, לאחר שהמצביא הרומי קווינטוס ססיליוס מטלוס הביס את אנדריסקוס (מתחזה שטען לכתר של מוקדון) בשנת 148 לפנה"ס. הפרובינקיה כללה את אפירוס וטוס, תסאליה, וחלקים מאיליריה ותראקיה. במאה ה-3 או במאה ה-4, מוקדון חולקה למוקדון פרימה (בדרום) ולמוקדון סאלוטאריס (בצפון).
ימי הביניים.
שבטים סלאביים דרומיים התיישבו בטריטוריה של רפובליקת מקדוניה הצפונית של ימינו במאה ה-6 והם נקראים על ידי היסטוריונים ביזנטיים יווניים "סקלאבינים". הסקלאבינים השתתפו במספר מתקפות כנגד האימפריה הביזנטית – לבד או בסיוע של הבולגרים או האווארים. בסביבות שנת 680 הקבוצה הבולגרית, בהובלתו של החאן קוּבר (שהשתייך לאותו שבט כמו אספרוך (שליט בולגריה)), התיישבה באזור פאלגוניה, ויזמה מספר תקיפות כנגד האזור של סלוניקי.
בשלהי המאה ה-7 יוסטיניאנוס השני ארגן מספר חילות משלוח גדולים כנגד הסקלאבינים מחצי האי היווני, שהצליחו לתפוס ולהגלות לקפדוקיה מעל 100,000 אנשים. בזמנו של קונסטנס השני (שנלחם גם כן בסלאבים), רוב התושבים הסלאביים של מקדוניה נתפסו והועברו למרכז אסיה הקטנה ושם נכפה עליהם להכיר בשלטונו של הקיסר הביזנטי ולשרת בצבא שלו.
אין תיעודים ביזנטיים של "סקלאבינים" לאחר 836/837 כיוון שהסלאבים של מקדוניה הוטמעו לתוך האימפריה הבולגרית הראשונה. ההשפעה הסלאבית באזור התחזקה עם עליית כוחה של מדינה זו, שסיפחה אליה את רוב האזור ב-837. הקדושים קירילוס ומתודיוס, יוונים ביזנטיים, שנולדו בסלוניקי, יצרו את האלפבית הגלגוליטי הסלאבי הראשון ואת השפה הסלאבית הכנסייתית העתיקה, וכן הם היו שליחים נוצריים לאזור הסלאבי כולו. המורשת התרבותית שלהם נרכשה והתפתחה בבולגריה של ימי הביניים, היכן שלאחר שנת 885 האזור של אוחריד הפך למרכז כנסייתי חשוב כאשר הקדוש קלמנט מאוחריד קיבל את התואר "הארכיבישוף הראשון בשפה הבולגרית" (בנוסף, הכנסייה נתנה לקלמנט מקום מגורים באזור). ביחד עם הקדוש נָאוּם הוא יצר מרכז תרבותי בולגרי פורח באזור אוחריד, היכן שלמעלה מ-3,000 למדו באמצעות האלפבית הגלגוליטי והקירילי במה שידוע כיום בשם בית הספר לספרות של אוחריד.
בשלהי המאה ה-10 רוב האזור של רפובליקת מקדוניה הצפונית של ימינו הפך למרכז הפוליטי והתרבותי של האימפריה הבולגרית הראשונה תחת שלטונו של הצאר סאמואיל מבולגריה, בעוד שהקיסר הביזנטי בסיליוס השני בולגרוקטונוס כבש את החלק המזרחי של המדינה, כולל את הבירה פרסלאב, ב-972. עיר בירה חדשה נוסדה באוחריד, והיא הפכה גם למקום המושב המרכזי של הפטריארכיה הבולגרית. החל מנקודת הזמן הזו, התרבות הבולגרית הפכה לחלק חשוב בתרבות הסלאבית הכוללת. לאחר מספר עשורים של לחימה רצופה, בולגריה נכנעה לאימפריה הביזנטית ב-1018 וכל האזור המקדוני שולב בתוך האימפריה הביזנטית כמו גם הפרובינציה של בולגריה, והפטריארכיה הבולגרית הורדה לדרגה של ארכיבישופות.
במאה ה-13 ובמאה ה-14 השליטה הביזנטית באזור התרופפה בעקבות שליטה של בולגרים וסרבים באזור. לדוגמה, קונסטנטין אסן, אציל מסקופיה לשעבר, שלט כצאר הבולגרי מ-1257 עד 1277. לאחר מכן, סקופיה הפכה לבירת האימפריה הסרבית תחת שלטונו של סטפן אורוש הרביעי דושאן, ולאחר התפוררות האימפריה, האזור נשלט על ידי אצילים סרביים מבית מרניאבצ'ביץ' ומבית דראגאש. האזור הריבוני של בית מרניאבצ'ביץ' כלל את החלקים המערביים של רפובליקת מקדוניה של ימינו ואילו האזור של בית דראגאש כלל את החלקים המזרחיים. בירת המדינה של בית מרניאבצ'ביץ' הייתה פרילפ. ישנם רק שני שליטים מבית מרניאבצ'ביץ' שידוע עליהם – המלך ווקאשין מרניאבצ'ביץ' ובנו, הנסיך מרקו. הנסיך מרקו הפך לשליט בובה של האימפריה העות'מאנית ומאוחר יותר הוא נהרג בקרב רובינה.
התקופה העות'מאנית.
לאחר שנכבש על ידי הצבא העות'מאני במחצית הראשונה של המאה ה-15, האזור היה בשליטתה של האימפריה במשך 500 שנים בקירוב, שבמהלכן נוצר בו מיעוט של טורקים, ובייחוד במובן הדתי של מוסלמים; רוב המוסלמים הללו הם אנשים שנכפה עליהם להמיר את דתם. במהלך תקופת השלטון העות'מאני, סקופיה ומונאסטיר (ביטולה) היו ערי הבירה של פרובינציות עות'מאניות נפרדות.
עמק הנהר וארדר, שמאוחר יהפוך לאזור המרכזי של רפובליקת מקדוניה, היה תחת שלטון עות'מאני לפני מלחמת הבלקן הראשונה ב-1912, למעט תקופה קצרה ב-1878 שבה הוא שוחרר בעקבות מלחמת רוסיה-טורקיה בשנים 1877–1878, כאשר הוא הפך לחלק מבולגריה. ב-1903, נוסדה רפובליקת קרושבו קצרת הימים בחלק הדרום מערבי של מקדוניה הצפונית של ימינו על ידי המורדים של ההתקוממות האילינדנית-פראובאז'נית. הרפובליקה הזו, הראשונה בתקופה המודרנית בבלקן, שרדה במשך 10 ימים בלבד – בין ה-3 באוגוסט עד ה-13 באוגוסט, ובראשה עמד הנשיא ניקולה קארב.
1912–1944.
האזור נכבש על ידי ממלכת סרביה במהלך מלחמת הבלקן הראשונה ב-1912 וסופח לסרביה בעקבות הסכמי השלום שסיימו את המלחמה. לאזור לא הייתה אוטונומיה כלשהי והוא נקרא Juzna Srbija (דרום סרביה) או Stara Srbija (סרביה הישנה).
לאחר מלחמת העולם הראשונה ממלכת סרביה הצטרפה לממלכת הסרבים, הקרואטים והסלובנים. ב-1929 הממלכה שינתה את שמה באופן רשמי לממלכת יוגוסלביה וחולקה לפרובינציות שנקראו באנובינות (banovinas). העיר סקופיה הפכה לבירתה של הטריטוריה של פרובינציית וארדאר, והטריטוריה כללה את מה שלימים יהפוך לרפובליקת מקדוניה.
במהלך מלחמת העולם השנייה פרובינציית וארדאר הייתה כבושה בין 1941 ו-1944 על ידי אלבניה (שהייתה תחת שלטונה של איטליה הפשיסטית), שסיפחה את האזורים המערביים שעיקר אוכלוסייתם הייתה אלבנית, ועל ידי בולגריה הפרו-גרמנית, שכבשה את שאר האזור. כוחות הכיבוש רדפו את תושבי האזור שהתנגדו למשטר; רדיפות אלו דחפו חלק מהתושבים להצטרף למחתרת הקומוניסטית של יוסיפ ברוז טיטו. אולם, חלק מהחיילים בצבא הבולגרי גויסו מהאוכלוסייה המקומית, שהיוותה עד 40% בחלק מהגדודים.
1944–1949.
בעקבות מלחמת העולם השנייה יוגוסלביה הוקמה מחדש כמדינה פדרלית תחת הנהגתה של המפלגה הקומוניסטית היוגוסלבית של טיטו. כאשר פרובינציית וארדאר לשעבר נוסדה ב-1944, רוב השטח שלה עבר לרפובליקה נפרדת בעוד שהחלקים הצפוניים ביותר נשארו בסרביה. ב-1946 הרפובליקה החדשה קיבלה מעמד חדש כאוטונומיה שנקראת "הרפובליקה העממית של מקדוניה" במסגרת הרפובליקה הסוציאליסטית פדרלית של יוגוסלביה. בשנת 1963 נוסחה חוקה ליוגוסלביה ששינתה במקצת את שם המדינה, כך שהוא יתאים לרפובליקות היוגוסלביות האחרות, ומעתה היא נקרא "הרפובליקה הסוציאליסטית של מקדוניה".
יוון הייתה מודאגת מהיוזמות של הממשלה היוגוסלבית, כיוון שהן רמזו על האפשרות לתביעות טריטוריאליות עתידיות על הפרובינציה היוונית "יוון הצפונית" שהייתה עיקר השטח של מקדוניה ההיסטורית ונקראה גם כן 'מקדוניה' באופן רשמי. כמו כן, הרשויות היוגוסלביות עודדו את פיתוח הזהות האתנית המקדונית והשפה המקדונית. השפה המקדונית הוכנסה באופן רשמי לספר החוקים ב-1944. דבר זה הכעיס עוד יותר הן את יוון והן את בולגריה, בגלל התביעות הטריטוריאליות האפשריות של המדינות החדשות לחלקים שהן קיבלו ממקדוניה לאחר מלחמות הבלקן.
במהלך מלחמת האזרחים ביוון (1944–1949), מקדונים רבים (ללא קשר לאתניות) השתתפו במחתרת ELAS שהוקמה על ידי המפלגה הקומוניסטית היוונית. ELAS ויוגוסלביה היו בקשרים טובים עד 1949, בעקבות חוסר רצונו של טיטו לעמוד לצידו של סטלין. לאחר תום המלחמה לא כל הלוחמים של ELAS שמצאו מקלט בדרום יוגוסלביה ובבולגריה הורשו לחזור ליוון: רק אלו שהחשיבו את עצמם כיוונים הורשו לחזור, בעוד שנאסרה כניסתם של אלה שהחשיבו את עצמם כבולגרים או מקדונים. מאורעות אלו תרמו גם כן ליחסים הרעים בין יוון ויוגוסלביה במקדוניה.
שנות ה-90.
ב-8 בספטמבר 1991 הרפובליקה הסוציאליסטית של מקדוניה ערכה משאל עם שתוצאתו תמכה בקבלת עצמאות מיוגוסלביה, תחת השם הרפובליקה של מקדוניה. השאלה במשאל העם הייתה:
בולגריה הייתה המדינה הראשונה שהכירה במקדוניה כשם החוקתי של המדינה החדשה. אולם, ההכרה הבינלאומית במדינה החדשה התעכבה בעקבות ההתנגדות של יוון לשימוש במה שנראה כסמלים ושמות הלניים, כמו גם לסעיפים בעייתיים בחוקת הרפובליקה. סיבוך נוסף היה שהאו"ם הכיר במדינה תחת השם "הרפובליקה היוגוסלבית לשעבר של מקדוניה".
יוון לא הייתה מרוצה גם מהחלטה זו של האו"ם והטילה מגבלות סחר בפברואר 1994. המגבלות בוטלו בספטמבר 1995 לאחר שמקדוניה שינתה את הדגל שלה והסעיפים בחוקה שהעניקו לה את הזכות להתערב בענייני פנים של מדינות אחרות. היחסים בין שתי המדינות התחממו במהירות, אולם שמה של המדינה נשאר מקור למחלוקת מקומית ובינלאומית. השימוש בכל אחד מהשמות נחשב למעורר מחלוקת בקרב הקבוצה התומכת בשם השני.
לאחר שהמדינה התקבלה לאו"ם תחת השם הזמני "הרפובליקה היוגוסלבית לשעבר של מקדוניה", ארגונים בינלאומיים אחרים אימצו גם כן את הנוהג הזה. רוב המדינות החברות באו"ם הכירו במדינה בתור הרפובליקה של מקדוניה, כולל ארצות הברית, בעוד ששאר המדינות עשו שימוש בשם הזמני "הרפובליקה היוגוסלבית לשעבר של מקדוניה", או שלא קיימו איתה יחסים דיפלומטיים כלל.