Intimate partner violence (IPV) is recognized as an important public health and social problem, with far-reaching consequences for women’s physical and emotional health and social well-being, yet little is known about how behavior change campaigns (BCCs) affect this type of behavior and other related abuses in Tanzania and in other sub-Saharan African countries. UZIKWASA is a civil society organization based in Pangani District in coastal Tanzania and since 2009 has conducted BCCs focused on promoting gender justice and effective leadership. As with other complex programs there is a question about how such approaches affect norms and practice in relation to violence against women and girls. Drawing on longitudinal research utilizing more than 1000 community diary entries (hearsay ethnographies) and qualitative methods using 20 in-depth interviews and 16 focus group discussions with women and men, and adolescent girls and boys, this article explores the ways in which UZIKWASA’s program effects change. The findings reveal personal and community narratives about gender-based and IPV as forms of retributive justice and assertion of authority by men. Drawing on gender performance as an explanation for violence, the research revealed changes in norms and practice in relation to violence against women and girls. Thus, we argue that UZIKWASA is gender-transformative by addressing gender norms and the critical awareness among leaders and the community of the social construction and reconstruction of gender that creates the context for real impact on changes in behavior.