Within Kenya, an estimated quarter of a million children live on the streets, and 1.8 million children are orphaned. In this study, we analyze how HIV contributes to the phenomenon of child-street migration. We interviewed a random community sample of caregiving women (n = 1974) in Meru County, Kenya, using a structured questionnaire in summer 2015. Items included reported HIV prevalence of respondent and her partner, social support, overall health, school enrollment of biologically related children and whether the respondent has a child currently living on the streets. Controlling for alcohol use, education, wealth, age and household size, we found a positive-graded association between the number of partners living with HIV and the probability that a child lives on the street. There was little difference in the odds of a child living on the street between maternally affected and paternally affected households. Lower maternal social support, overall health and school enrollment of biologically related children mediated 14% of the association between HIV-affected households and reporting child-street migration. Street-migration of children is strongly associated with household HIV, but the small percentage of mediated effect presents a greater need to focus on interactions between household and community factors in the context of HIV. Programs and policies responding to these findings will involve targeting parents and children in HIV-affected households, and coordinate care between clinical providers, social service providers and schools.