In this study we investigate reasons for the existence of the stable private sector wage “premium” in the Russian labor market for the period of 1994–2014 using data from the Russian Longitudinal Monitoring Survey. Public sector in our study is subdivided into budget sector and SOE sector. In contrast to the European labor market we do not find evidences of significantly higher job security in the public sector but we do establish that differences in fringe benefits could explain at least 50% of the wage gap. Difference in fringe benefits constitutes of discrepancies in the access to regular paid vacation and payments for tourist camps, full or partial payments for treatments in medical facilities, subsidies for food and transportation, free childcare etc. Lower wages in the public sector can also be explained by shorter workweek and more flexible working conditions, however the contribution of these factors to the private-public wage gap is negligible. We establish that the reasons for the existence of the private sector wage “premium” discussed above are applied to the same extend both to employees in public sector and in the SOE.