A paradoxical pattern in domestic labor has long been observed in family studies. Although women undertake the majority of domestic work, they usually perceive their division of house work as fair. This fairness paradox suggests that beliefs about the appropriate allocation of house work are even more resistant to social changes than the actual division of household labor. Accordingly, an investigation of the change in perceptions of housework division over time contributes to a better understanding of the mechanisms that lead to the change in gender relations in the household and broader society. Using data from the 2002 and 2012 ISSP Family and Changing Gender Roles Module, this research examines the individual and country-level factors that relate to the changes in women’s perceived unfairness of housework division across 23countries from 2002 to 2012. According to our results, the increase in female employment and growing enrollment in formal childcare facilities and preschools are associated with elevated levels of women’s perceived unfairness of housework division, whereas an extension of the length of parental leave is negatively correlated with the increase in women’s perceived unfairness. The findings suggest the availability of formal childcare and a more gender-equal economic structure contribute to women’s growing sense of entitlement to a more equal division of domestic work, whereas extended parental leave may intensify gender traditionalism in the household.