This paper evaluates a randomized controlled trial of the Nurse-Family Partnership (NFP) program conducted in Memphis, TN in 1990. NFP offers home visits conducted by nurses for disadvantaged first-time mothers during pregnancy and early childhood. We test NFP treatment effects using permutation-based inference that accounts for the NFP randomization protocol. Our methodology is valid for small samples and corrects for multiple-hypothesis testing. We also analyze the underlying mechanisms generating these treatment effects. We decompose NFP treatment effects into components associated with the intervention-enhanced parenting and early childhood skills. The NFP improves home investments, parenting attitudes and mental health for mothers of infants at age 2. At age 6, the NFP boosts cognitive skills for both genders and socio-emotional skills for females. These treatment effects are explained by program-induced improvements in maternal traits and early-life family investments. At age 12, the treatment effects for males (but not for females) persist in the form of enhanced achievement test scores. Treatment effects are largely explained by enhanced cognitive skills at age 6. Our evidence of pronounced gender differences in response to early childhood interventions contributes to a growing literature on this topic.