Patients co-infected with visceral leishmaniasis (VL) and HIV-1 (VL/HIV patients) suffer from recurrent VL relapses and increased mortality. The aim of our study was to test the hypothesis that HIV patients who present with their first episode of VL (primary VL/HIV patients) experience less relapses and lower mortality as compared to VL/HIV patients who have a previous history of VL relapses (recurrent VL/HIV patients). Our results show that primary VL/HIV patients have a lower parasite load and that their relapse-free survival is significantly longer. Relapses in both groups of patients occur independently of HIV viral load. Our clinical and immunological analyses of these patients at the time of diagnosis and during follow-up show that the poorer prognosis of recurrent VL/HIV patients is accompanied by lower weight gain and lower recovery of all blood cell lineages, as well as lower production of antigen-specific IFNg, lower CD4+ T cell counts and higher expression levels of the inhibitory receptor PD1 on CD4+ and CD8+ T cells. We propose that in addition to the current treatments, novel interventions should be considered at the time of VL diagnosis in VL/HIV patients and suggest that improved anti-leishmanial and antiretroviral treatments, as well as immune therapy, through PD1/PDL-1 blockade and/or through IFNg administration, could result in more efficient parasite killing and thereby reduce the relapse rate and improve survival.