Loss to follow-up contributes to the low coverage of HIV care interventions among HIV-exposed infants in Beira, Mozambique. This qualitative study explores the perceptions of HIV-infected women and their health care providers regarding the main obstacles preventing women from attending follow-up visits for HIV care, and factors influencing women’s decisions about newborn care. Fifty-two in-depth interviews and two focus group discussions were conducted; transcripts were coded and analyzed using ATLAS.ti. Interviewees perceived three major barriers to follow-up: food insecurity, difficulties navigating the health system, and women’s familial roles and responsibilities. Our findings unveil the complex context in which HIV-infected women and their children live, and suggest that the structure and function of the HIV care system should be reviewed. Economic empowerment of women is crucial to achieving better compliance with medical care. Integration of mother and child services and more efficient and culturally sensitive medical services may improve follow-up.