The third decade after the Velvet revolution in 1989, which restored political freedom and democracyin Czechoslovakia, has found its two successors – the Czech republic and Slovakia – in the midst of, whatsome authors describe as, a crisis of legitimacy of state institutions in Western countries. The perception oflegitimacy and the trust in institutions of criminal justice play pivotal role in securing and maintainingsocial consensus and harmonious development of societies. Economic and political turbulences during theera of transformation to the free market economies especially in the 1990s have contributed, in author’s view,to an unfortunate state of a very low trust of the Czech and Slovak citizenry in how their criminal justice institutionsexercise entrusted powers and perform their duties. A question thus emerges, what should be doneto sustain and foster legitimacy of criminal justice institutions in the context of contemporary developmentof these relatively young democracies? The article firstly turns to a discussion in the literature of English andAmerican provenience with the aim to analyse the meaning and importance of democratic legitimacy ofcriminal justice institutions. A special focus is dedicated to the notion of ‘procedural justice‘, i.e. perceivedfairness of how these institutions exercise their authority, and supposed limitations of this concept for achievinghigher perception of legitimacy and law-abidance among population. Further, some complementingaims, such as endeavours to reach ‘materially’ just outcomes, or focuses on professionalization and higherefficiency in exercising entrusted powers, are being discussed. The author finally submits that, in order to sustainand foster institutional legitimacy in evolving Czech and Slovak democracies, much more attention hasto be paid to ensure that criminal justice institutions, i.e. the police, the public prosecution, the judiciary andthe correctional service, exercise their duties in a procedurally just, fair and respectful manner, in consistencywith the principle of proportionality, and in an effective and proficient pursuit of security.