Историята за решаване на спора за името започна с предложението „Нова Македония“ още през 1992 г. и от тогава на масата се появиха редица предложения, включително „Република Македония-Скопие“, „Конституционна република Македония“, „Демократична република Македония“, „Независима Република Македония „, а после „Република Нова Македония“,“ Република Македония (Скопие), „Република Горна Македония“, „Горна Република Македония“…
Всичко започна с плана на португалския външен министър Жоао Пинейру. В плана му има три документа. Първият е гаранции „срещу териториални претенции“, вторият е за допълнителни гаранции „срещу враждебна пропаганда“ и третият е предложението на Пинейру за „Нова Македония (New Macedonia)“ като удобно име на държавата, пише македонският сайт МКД.мк.
На 8 април 2005 г. посредникът на ООН Матю Нимиц излезе с предложението „Republika Makedonija-Skopje“ за официално използване на форуми и в международните отношения, а трети страни могат да избират какво име ще използват, дали това или конституционното име на Македония.
През октомври 2005 г. Нимиц излезе с известната „тройна формула“. Тази формула предвиждаше „Republic of Macedonia“ за международна употреба и за тези страни, които вече са признали Македония под това име, Гърция да използва формулата „Republika Makedonija-Skopje“, а „Republika Makedonija“ да се използва в международни организации и в ООН . Националността според това предложение е трябвало да бъде „граждани на Република Македония“.
Нимиц тук добавя две допълнения, първото е името „Republika Makedonija“ да бъде до 2008 г., а след това „Republic of Macedonia“. Второто предвижда подновяване на прегледа на споразумението след 15 години, в което се казва, че никой не може да има изключителното право на името Македония.
Географското определение „Горна“, което все още е актуално, дори и желано от гръцка страна, поне според изявленията оттам, се появи в плана от осем точки, предложен от Нимиц през февруари 2008 година. В този план той посочи „Конституционна република Македония“, „Демократична република Македония“, „Независима република Македония“, „Нова Македония“ или „Република Горна Македония“. Според предложението едно от тези имена е трябвало да бъде използвано в международни организации и за двустранни отношения с Гърция. Освен това в предложението се посочва, че „Македония (Macedonia)“ и „македонски (Macedonian)“ могат да използват и двете страни, но само в съответствие с действащото международно законодателство, конвенции и практики, включително използването на географски имена за търговски или други подобни цели, но никой няма да има изключително (политическо или търговско) право на името Македония. Това предложение предвижда и промяна на македонските паспорти.
Един месец по-късно Нимиц излезе с преработен план от осем точки, който предвижда освен конституционното име, Македония или „втората страна“ като официално международно име за международни организации, договори, конвенции и споразумения да използва едно от предложенията „Република Горна Македониja“, „Нова република Македониja „,“ Република Нова Македониja „или“ Република Македониja-Скопjе“, всички на английски език. Това име би било и в паспортите на македонските граждани, а думата „Македония“ сама по себе си не може да се признае като официално име, формално или неформално.
Много скоро след това предложение Нимиц излиза с това, което нарича „окончателно“ предложение, на 25 март, с леко променено съдържание.
Това предложение предлага име с географско определение за цялостна употреба. Конституционното име на кирилица, Република Македониja може да се използва за вътрешна употреба и „Република Македониja (Skopje)“ в международните отношения. За двустранните отношения се предлага „Republic of Macedonia (Skopje)“, с което на трети страни, които са признали Македония под нейното конституционно име „им се внушава“, но няма да бъдат “ насилвани“ да променят решението. Термините „Macedonia“ и „Macedonian“ ще бъдат свободни за използване и двете страни.
Допълнителни точки в това предложение са двете страни да зачитат добросъседските отношения и Гърция ще подкрепи интеграцията на Македония в ЕС и НАТО.
През октомври 2008 се появи ново предложение на Нимиц, в което се казва, че „Republic of Macedonia“ ще остане официално име за вътрешна употреба, но на македонски език, а за официална употреба в ООН, ЕС и НАТО например ще бъде „Republic of North Македония „(Република Северна Македония). Съветът за сигурност на ООН ще предложи на трети държави да използват името „Republic of North Macedonia“.
Според това предложение на първа страница на паспортите ще бъде „Republic of North Macedonia“ на английски език, „Republique de Macedoine du Nord“ на френски и
„Република Македониja” на македонски. Освен това и двете страни ще потвърдят, че нямат териториални претенции един срещу друг.
Предложението, което се появи на 7 юли през следващата 2009 г., се води като „пречистен“ и предвижда име „Republic of North Macedonia“ за всички цели, освен за вътрешна, за която остава конституционното име.
Под заглавие „Предложение“ на две страници и с 10 точки излезе предложението на Нимиц от 9 април 2013 г., което се основава на името „Горна Република Македонија“.
Официално име би било Upper Republic of Macedonia, обхватът на употреба „erga omnes“, без двустранна и домашна употреба, езика „Macedonian / Makedonski“ и гражданството (nationality), „of the Upper Republic of Macedonia“; алтернативен Makedonsko/Macedonian”.
Предложението предвижда само препоръка до държавите-членки на ООН да използват новото име във всички официални контексти и дава възможност името Република Македониja да бъде използвано в страната. По отношение на езика, Нимиц предлага той на английски да се назначава със съставното „Macedonian / Makedonski“, което може да се смята за компромис между македонското настояване за тази цел да се използва терминът „Macedonian“ и позицията на Гърция от този период, че най-многото, което може да бъде договорено, е въвеждането на термина „Makedonski”, както оригинално се нарича език, с латинска транскрипция.
