This article presented to the attention of readers is dedicated to the analysis of history, present condition and development prospects of inter-state relations on national and regional security between former Soviet republics, now new sovereign Eurasian states, as well as to the examination of organization forms of such relations. Having formulated basic principles of cooperation on these issues and underlying the need of collective and coordinated activities against threats to their security and stability in new geopolitical realities stipulated by the collapse of the USSR nine post-Soviet states concluded the Collective Security Treaty which came into force in 1994. Five years later, in April 1999, presidents of six these countries, namely Armenia, Belarus, Kazakhstan, Kyrgyzstan, Russia and Tajikistan, signed the protocol on prolongation of the Collective Security Treaty for the next five years while Azerbaijan, Georgia and Uzbekistan refused to extend their membership in the Treaty and left it. It happened since due to a number of various domestic and external reasons the formation of national statehood of new sovereign states began to differ substantially from each other as to their strategic goals, aspirations and orientations which subsequently caused serious changes in their approaches to building relations with their foreign partners in bilateral and multilateral forms. In this connection in May 2002 those countries that retained their membership in the Collective Security Treaty decided to reorganize it into a new alliance with a higher degree of integration of its members in order to increase its role in promoting national and regional security - the Collective Security Treaty Organization. The present article examines basic events connected with the Collective Security Treaty Organization formation over the next 20 years, evolution of its goals and tasks, as well as requirements of making concrete directions of its activities more precise because of fundamental changes in the international environment. In the course of the undertaken analysis most important achievements of the Collective Security Treaty Organization during these years were singled out as well as concrete shortcomings in its activities were noted. Also, alternative variants of further development of this international security organization including those that may exceed the post-Soviet space were mentioned.