Visceral leishmaniasis (VL) has emerged as a clinically important opportunistic infection in HIV patients, as VL/HIV co-infected patients suffer from frequent VL relapse. Here, we follow cohorts of VL patients with or without HIV in Ethiopia. By the end of the study, 78.1% of VL/HIV—but none of the VL patients—experience VL relapse. Despite a clinically defined cure, VL/HIV patients maintain higher parasite loads, lower BMI, hepatosplenomegaly, and pancytopenia. We identify three immunological markers associated with VL relapse in VL/HIV patients: (1) failure to restore antigen-specific production of IFN-γ, (2) persistently lower CD4+ T cell counts, and (3) higher expression of PD1 on CD4+ and CD8+ T cells. We show that these three markers, which can be measured in primary hospital settings in Ethiopia, combine well in predicting VL relapse. The use of our prediction model has the potential to improve disease management and patient care.