Abstract Background Nutrition training can boost competence of health workers to improve children’s feeding practices. In this way, child undernutrition can be ameliorated in general populations. However, evidence is lacking on efficacy of such interventions among Human Immunodeficiency Virus (HIV)-positive children. We aimed to examine the efficacy of a nutrition training intervention to improve midlevel providers’ (MLPs) nutrition knowledge and feeding practices and the nutrition statuses of HIV-positive children in Tanga, Tanzania. Methods This cluster-randomized controlled trial was conducted in 16 out of 32 care and treatment centers (CTCs) in Tanga. Eight CTCs were assigned to the intervention arm and a total of 16 MLPs received nutrition training and provided nutrition counseling and care to caregivers of HIV-positive children. A total of 776 pairs of HIV-positive children and their caregivers were recruited, of whom 397 were in the intervention arm. Data were analyzed using instrumental variable random effects regression with panel data to examine the efficacy of the intervention on nutrition status through feeding practices. Results Mean nutrition knowledge scores were higher post-training compared to pre-training among MLPs (37.1 vs. 23.5, p