The authors examine the issues of providing legal relevance of e-documents within the cross-border cooperation of the Collective Security Treaty Organization (CSTO) member states. They focus on the analysis of legal, technological and organizational barriers that hinder the single electronic document management, and point to the discrepancies in national laws, interoperability problems, and lacking trusted environment. The urgency of the study is inspired by strategic significance of paperless technologies for making decisions in the sphere of regional security. Based on the analysis of open ICT country procurements and Eurasian Economic Commissions reports (EAEU Digital Agenda), the authors estimate the market of CSTO cross-border electronic document management at 18-22 billion rubles with the potential of 2.5-3 times growth provided that the barriers are eliminated. The purpose of the study is to reveal system problems and to develop scientifically well-ground solutions for e-document legal relevance. The complex methodology was applied, i. e. detailed comparative legal analysis of the legislations of CSTO member states (the framework laws on electronic signature and electronic documents: RF FZ No. 63, Republic of Kazakhstan Law No. 370-II, Republic of Belarus Law No. 113-З, along with specialized technical regulations); system approach; legalistic and institutional approaches.