In this paper, we look at the evolution of the change in the wage structure 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 and increasing returns to human capital. Moreover, exploiting the linked employer-employee character of the data set, we document changes in within-firm wage dispersion and between-firm dispersion. We investigate various hypotheses related to transition towards a market economy, increased domestic and international competition, an increasingly decentralized wage bargaining and a changing educational composition of the workforce to explain these patterns. We find some support that these factors have contributed to the changes in the Czech wage structure, although the latter is the most strongly associated with the observed changes in wage inequality.