In this paper, we look at the evolution of the Czech labor market, and its wage structure in particular, using a linked employer-employee dataset covering a large fraction of the Czech labor market over the period 1998-2006. We find evidence of (slightly) diminishing gender inequality, increased returns to human capital, especially to education. We investigate various hypotheses to explain that pattern. Moreover, we document a strong increase in within-firm wage dispersion and an only moderate increase in between-firm dispersion. We investigate various hypotheses related to transition towards a market economy, increased domestic and international competition and an increasingly decentralized wage bargaining to explain these patterns.