In the Post-Cold War era, NATO enlargements occurred in two rounds. Ten new member states joined NATO. These enlargements represent a major asset to the building of new security architecture of the Post-Cold War Europe, after the dissolution of Warsaw Treaty and the USSR. Two rounds of NATO enlargement were very different by their territorial reach, regional determination, current circumstances inside the Alliance and the influence on geopolitical relations in Europe and the US-Russia geostrategic relations. NATO enlargements were precursory to the EU enlargements on ten post-communist European states. After the September 11, successful implementation of the second round of NATO enlargement became one of the strategic objectives in struggle against terrorism, led by the USA and its allies. The enlargement significantly changed relations within NATO as well as the very geopolitical balance in Europe. The security and stability zone expanded to the East and Southeast of Europe. NATO’s influence has also spread over the border regions of Europe, even transcending those borders. Third round of NATO enlargement was announced at the NATO summit in Bucharest during which Croatia and Albania were invited to join the Alliance. The third round of NATO enlargement will probably refer to Macedonia, if it settles a dispute over its name with Greece. Given that NATO is to include the Western Balkans states, its role of a stabilization force will become even more important in this unstable area, particularly under the aspect problem of solutions to the problems connected with the independence of Kosovo and its consequences to the stability of the region. Future strategic challenges to the European security will be tied to the NATO-Russia relations, regarding the NATO’s future ambitions in the Eastern Europe and Caucasus region. If NATO decides to invite Georgia and Ukraine to become its members, we can expect Russian reaction, which could lead to the period of whole scale and long-term instability in a large part of Europe, but also in a part of Eurasia.