This paper studies the relationship between labor market institutions and policies and labor market performance using a new and unique dataset that covers the countries of Eastern Europe and Central Asia, which in the last two decades experienced radical economic and institutional transformations. We document a clear trend towards liberalization of labor markets, especially in the countries of the former Soviet Union, but also substantial differences across the countries studied. Our econometric analysis implies that institutions matter for labor market outcomes, and that deregulation of labor markets improves their performance. The analysis also suggests several significant interactions between different institutions, which are in line with the idea of beneficial effects of reform complementarity and broad reform packages. Finally, we show that there are important advantages of focusing on a broader set of labor market outcomes, and not only on the unemployment rate, which until now has been the main approach in the empirical literature.