Realizując cele polityczno-strategiczne Układu Warszawskiego gwarantujące wówczas zabezpieczenie nowego ładu w powojennej Europie, przy położeniu geostrategicznym Polski, obydwa państwa podpisały 18 listopada 1956 w Moskwie wspólną deklarację stwierdzającą, że strony będą się konsultować w sprawach pobytu radzieckich jednostek wojskowych na terytorium Polski, a w szczególności ich liczebności i składu oraz wypracowania zasad traktujących o wzajemnym poszanowaniu równości i suwerenności.
17 grudnia 1956 podpisano w Warszawie Umowę między Rządem Polskiej Rzeczypospolitej Ludowej a Rządem Związku Socjalistycznych Republik Radzieckich o statusie prawnym wojsk radzieckich czasowo stacjonowanych w Polsce (), sankcjonującą 12-letnią obecność tych wojsk i regulujący na obecny dzień i do dnia ich wycofania aspekty prawne ich pobytu. Zgodnie z treścią tej umowy zawarto później w latach 1956–1979 9 obustronnych aktów prawnych regulujących aspekty prawne czasowego stacjonowania wojsk radzieckich w Polsce. Władze polskie wydały 16 wewnętrznych aktów wykonawczych związanych z pobytem wojsk. 20 lipca 1957 został powołany pierwszy pełnomocnik rządu PRL ds. pobytu wojsk radzieckich w Polsce. Był nim gen. bryg.