This paper re-examines the meanings and interpretations of “socialist legality” after Stalin’s death. It suggests that it was in the 18 months after XX Congress in February 1956 and, in particular, after Hungarian uprising in October of that year that the principles of socialist legality articulated in the immediate wake of Stalin’s death were to come under greatest strain. Closer examination of this period thus serves as a litmus test of the degree to which the axioms of socialist legality had become fully institutionalized in the Soviet system. In the second part, the paper looks at the growing concern with the preservation of public order in 1950s and at how the institution tasked with preserving public order, the militsiia, often had a thin and perfunctory understanding of socialist legality which was much at odds with the standard interpretations of procurators and judges. Worse still, in a continuation of practices from the Stalin era, militsiia officials in late 1950s would come to be regarded as the main perpetrators of what would come to be known as “violations of socialist legality.”