Some of Macedonia's neighbours felt betrayed by this decision. Bulgaria believed Macedonia was Bulgarian, and Greeks that it was Greek.
The Macedonian nationality has always been the most contentious in the Balkans.
The protesters who stormed the Skopje parliament on 26 June are only the latest in a long line of contenders to be the authentic inheritors of the proud traditions and unsurpassed military achievements of the ancient Macedonian monarch Alexander the Great.
But modern Macedonia dates from the decisions of Tito and Stalin, who decided to set up a Macedonian republic within communist Yugoslavia after 1945, in the interests of Yugoslav communism.
Some of Macedonia's neighbours felt betrayed by this
decision. Bulgaria believed Macedonia was Bulgarian, and
Greeks that it was Greek.
Greece has never recognised the new republic by its preferred name of the Republic of Macedonia. Macedonia is also the name of a region of Greece.
Macedonians believe their little country is involved in a fight for survival, and that the "four wolves" of Greece, Albania, Bulgaria and Serbia - which surround it as its traditional enemies - are now poised yet again to strike.
The most nationalist party in Skopje is the Internal Macedonian Revolutionary Organisation (VMRO), led by Ljubco Georgievski, who in alliance with an ethnic Albanian party managed to displace the pro-Serb ex-communists as the majority party in government after 1998, and is now prime minister.
Many of this party's banners were to be seen during the riot outside the Skopje parliament, with Mr Georgievski locked in a power struggle with more moderate (but still ex-VMRO) President Boris Trajkovski.
Unstable foundations
These Macedonians, mostly from Skopje and the eastern part of the country, believe that their version of Macedonian identity is the correct one, and that Bulgaria and other neighbouring nations have never understood Macedonian history correctly.
Many of them feel that the 30% Albanian minority in the state is unwilling to give up its traditional culture to fully integrate with the Macedonian majority.
But there are other groups within Macedonia, such as the 10% Roma population, many Muslims came to Skopje from the Sandjak region which straddles Montenegro and Serbia to help reconstruct the city after the great earthquake 30 years ago, and parts of the population who more closely identify themselves as Serbs or Bulgarians.
Over 130,000 Serbs came as colonists to the northern
Macedonian territory when it was part of South Serbia under Royalist
Yugoslavia. Many called themselves Macedonians after World War II to
keep their privileged positions.
The dilemma for the international community in Macedonia is how to base a policy on such a potentially unstable and contentious foundation.
Many of the most politically influental of the Macedonia nationalists in Skopje politics do not accept the modern concept of a multicultural and pluralistic state, and adhere to communist-period concepts of monolithic Macedonian nationalism.
This makes it difficult for leaders, whether Boris Trajkovski or Ljubco Georgievski, to compromise with the reformist demands of the 30% Albanian minority, even if they would like to do so.