Direct exposure to counter-stereotypical behaviors early in life has been put forward as a promising way to change gender norms across generations. We ask to which extent public policy designed to promote counter-stereotypical behavior among parents influences gender norms for their children. Specifically, we combine the national-level introduction of paternity leave in Spain with a unique, large-scale lab-in-the-field experiment conducted with children born around the policy change. We provide causal evidence that, at age 12, children whose fathers were eligible for paternity leave exhibit more egalitarian attitudes towards gender roles and are more supportive of mothers and fathers being equally engaged in the labor market and in the home. They also engage more in counter-stereotypical day-to-day behaviors and expect to deviate from the male-breadwinner model in the future.