Using appropriate econometric methods and 11 representative household surveys, this paper empirically assesses the extent and evolution of gender discrimination in the South African labour market over the post-apartheid period. Attention is also paid to the role that anti-discriminatory legislation has had to play in effecting change in the South African labour market. Much of the paper’s focus is placed on African women who would have benefited most from the new legislative environment. African and, to a lesser extent, Coloured women received on average higher real wages than their male counterparts following changes in labour legislation. Oaxaca (1973) and Blinder (1973) decompositions reveal this to be due to both greater endowments of productive characteristics for African and Coloured women and declining gender discrimination that reached relative stability after 2000. Detailed Oaxaca-Blinder decompositions of the African gender wage gap reveal that the driving factor behind an increasing and negative explained component is improved distribution and returns to productive characteristics for women in certain occupations, as well as higher returns to education and employment in the public sector. However, African women are prevented from realising this in the form of higher earnings as a result of increasing returns to employment in certain industries for males. Decomposition results using the methodology of Juhn, Murphy and Pierce (1991, 1993) are suggestive of a sticky floor for African women in the South African labour market. The gender wage gap is therefore found to be wider at the bottom of the wage distribution than at the top.