This paper presents and discusses new data on employment protection legislation (EPL) in the successor states of the former USSR – the CIS and Baltic states – over 25 years from 1985 to 2009. We use the OECD methodology (OECD EPL, version II) for assessing the strictness of national labor laws with respect to employers’ firing costs. In addition to the overall OECD EPL index, we present detailed statistics for 18(22) sub-indicators used for its computation. The new data allow us to make several important observations. In particular, the data do not support the widely held view that labor regulations in the former USSR with respect to firing costs were extremely rigid and were subsequently liberalized by the 15 successor states over the course of transition to a market economy. Rather, the dynamics of the EPL index in the region resembles an inverted U-shaped pattern with the peak of labor market rigidity occurring in the mid-1990s in the CIS countries and a decade later in the Baltic States. In terms of major sub-indicators, we observe a rather unusual pattern: gradual liberalization of permanent contracts on the background of increasing regulation of temporary contracts and collective dismissals. This is in sharp contrast with the OECD economies, where liberalization of temporary contracts has been the major trend in the recent decades. By now, the ex-USSR states as a group do not differ that much from the EU-15 and OECD countries in terms of the overall EPL index, although they differ considerably in terms of contributions to the overall EPL of its thee major components, namely, regulation of permanent contracts, temporary contracts, and collective dismissals. We also show that our EPL data are correlated with a number of variables characterizing economic development, progress in market-oriented reforms, and political regimes prevailing in the countries studied, which suggests potential of using the new dataset in further politico-economic research.