We examine how the shift from state socialism affects gender inequality in the labor market using multivariate models of employment exit, employment entry, job mobility and new job quality for 3,580 Russian adults from 1991 through 1997. Gender differences changed in a complex fashion. Relative to men, women gained greater access to employment, but female disadvantage in the quality of new jobs widened. Although these two trends appear to be opposite, they are closely related. Both are connected to the introduction of market institutions, not gender differences in human capital or structural location in the labor market.