Changing behaviors is usually a core component of the role of community health workers (CHWs), but little is known about the mechanisms through which they change behavior. We collected qualitative data from 8 sites in Ethiopia and northern Nigeria where CHWs were active to understand how they change newborn care behaviors. In each country, we conducted 12 narrative interviews and 12-13 in-depth interviews with recent mothers and 4 focus group discussions each with mothers, fathers, grandmothers, and CHWs. We identified 2 key mechanisms of behavior change. The first was linked to the frequency and consistency of hearing messages that led to a perception that change had occurred in community-wide behaviors, collective beliefs, and social expectations. The second was linked to trust in the CHW, obligation, and hierarchy. We found little evidence that constructs that often inform the design of counseling approaches, such as knowledge of causality and perceived risks and benefits, were mechanisms of change.