Как и другие страны бывшей Югославии, Македония образовала свою футбольную сборную только в начале девяностых годов. Свой первый матч македонцы провели в октябре 1993 года со Словенией. Под руководством Андона Дончевски Македония сумела одержать весьма уверенную победу со счётом 4-1.
Однако после такого убедительного старта последовали неудачные игры со сборной Турции и уругвайским клубом "Пеньяролем". Македонцы искали всевозможных спаррингов, но играть с новообразованной командой желающих было немного. Первой отборочной кампанией Македонии стала квалификация на чемпионат Европы 1996 года. Македония попала в группу к Испании, Дании, Бельгии, Кипру и Армении. Игра против сборной Дании стала первой официальной для македонцев и завершилась со счётом 1-1, причем свой гол Македония забила уже на четвёртой минуте. После этого последовало поражение от Бельгии со счётом 5-0, которое и по сей день является одним из самых крупных для македонцев. Тот турнир "красные львы" завершили на четвёртой позиции с семью очками.
Отборочный путь на чемпионат мира 1998 года Македония начала матчем против Лихтенштейна, который выиграла со счётом 3-0. В ответной игре македонцы и вовсе сумели добиться крупнейшей на данный момент победы со счётом 11-1. Команда провела весьма неплохой розыгрыш, завершив его на всё той же четвёртой строчке, но уже с тринадцатью очками.
Вообще четвёртое место в группе стало для Македонии заколдованным. На этой позиции команда закончила три следующих отборочных цикла: на чемпионат Европы-2000, на чемпионат мира-2002 и Евро-2004. Ни в одной из них македонцы всерьёз не претендовали на выход из группы, а турнир к чемпионату Европы в Португалии и вовсе стал худшим. Македония сумела набрать всего шесть очков. Проведя работу над ошибками, македонцы выглядели уже совсем иной командой к отборочному циклу на чемпионат мира-2006. Начав с победы над Арменией, македонцы сенсационно сыграли вничью с Голландией. Но, окрыленные успехом футболисты, слишком рано расслабились и ухитрились проиграть сборной Андорре. Затем было поражение 6-1 от Чехии и итоговое пятое место с девятью очками.
В 2006 году начался отбор на Евро-2008. Македония, в целом, провела весьма неплохой турнир и набрала целых четырнадцать очков, но из-за высокой плотности в группе македонцы оказались только на пятой позиции, опередив лишь Эстонию и Андорру. С Россией и Андоррой македонцы встретились и в отборочном цикле на Евро-2012. Результат оказался уже до боли привычным – предпоследнее место с восемью очками.
Самые крупные победы: Македония 11-1 Лихтенштейн (9 ноября 1996)
Самые крупные поражения: Македония 0-5 Бельгия (7 июня 1995) Македония 0-5 Словакия (7 октября 2001) Венгрия 5-0 Македония (14 ноября 2001) Чехия 6-1 Македония (8 июня 2005)