The Gini coefficient of labor earnings in Brazil fell by nearly a fifth between 1995 and 2012, from 0.50 to 0.41. The decline in other measures of earnings inequality was even larger, with the 90-10 percentile ratio falling by almost 40 percent. Applying micro-econometric decomposition techniques, this study parses out the proximate determinants of this substantial reduction in earnings inequality. Although a falling education premium did play a role, in line with received wisdom, this study finds that a reduction in the returns to labor market experience was a much more important factor driving lower wage disparities. It accounted for 53 percent of the observed decline in the Gini index during the period. Reductions in horizontal inequalities - the gender, race, regional and urban-rural wage gaps, conditional on human capital and institutional variables - also contributed. Two main factors operated against the decline: a greater disparity in wage premia to different sectors of economic activity, and the "paradox of progress": the mechanical inequality-increasing effect of a more educated labor force when returns to education are convex.