Background: Globally, up to 26% of children under-five years of age were stunted and 16% were underweight in 2011, which is the 35% decrease in stunting and a 36% decrease in underweight in 1990. The prevalence of stunting and underweight were shown to be higher in Africa about 35.6% and 17.7% respectively.The prevalence of stunting has shown to be 34.7% at the national level, while in Mbeya region it was 36%. It reflects the existence of chronic malnutrition in the country. Objectives To determine the prevalence and factors associated with malnutrition in under five children born to HIV positive mothers attending Mbeya referral hospital in the study period i.e. May and June 2016. Methodology The study was a hospital based cross section study. This study was conducted in May and June in 2016. The study population was all under five children attended in pediatric department at Mbeya referral Hospital in May and June 2016 which is the study period. Interviews using questionnaires was used to collect data from children. Data were entered and analyzed using SPSS. Results Of the 203 enrolled children, the prevalence ofprevalence of stunting, underweight and wasting were 38.4%, 28.6% and 15.7% respectively. Analysis of this study indicated place of residence of a child and primary education of mother were found to be significantly associated with stunting. Underweight is shown to be statistically significant associated children whose mothers had secondary education or more, and the prevalence of wasting is significantly associated with the children clinical condition or sickness at the time of interview was taken. Conclusion This study revealed that, prevalence of malnutrition is high and it is among the health problems in Mbeya city. The prevalence statistics in this study area were higher than regional and national figures found on TNNS SMART Survey of 2014. Intervention should focus on reviewing the education curriculums so as to deliver quality education and improving economic status thereby the health conditions.