This paper examines the extent to which under five children in households or communities adversely affected by HIV/AIDS are disadvantaged, in comparison with other children in less affected households/communities. The study is based on secondary analysis of the Demographic and Health Survey (DHS) data collected during 2003–2008 from 18 countries in sub-Saharan Africa, where the DHS has included HIV test data for adults of reproductive age. We apply multilevel logistic regression models that take into account the effect of contextual community/country level HIV/AIDS factors on child malnutrition. The outcome variable of interest is child undernutrition: stunting, wasting and underweight. The results suggest that across countries in sub-Saharan Africa, children whose mothers are infected with HIV are significantly more likely to be stunted, wasted or underweight compared to their counterparts of similar demographic and socio-economic background whose mothers are not infected. However, the nutritional status of children who are paternal orphans or in households where other adults are HIV positive are not significantly different from non-orphaned children or those in households where no adult is infected with HIV. Other adult household members being HIV positive is, however, associated with higher malnutrition among younger children below the age of one. Further analysis reveals that the effect of mothers’ HIV status on child nutritional status (underweight) varies significantly across communities within countries, the effect being lower in communities with generally higher levels of malnutrition. Overall, the findings have important implications for policy and programme efforts towards improved integration of HIV/AIDS and child nutrition services in affected communities and other sub-groups of the population made vulnerable by HIV/AIDS. In particular, children whose mothers are infected with HIV deserve special attention.