The use of culture and a nested polymerase chain reaction (PCR) of blood in predicting the probability of relapse was evaluated in 20 patients co-infected with Leishmania and human immunodeficiency virus (HIV). Fourteen of 20 patients relapsed, with 24 clinical relapses diagnosed. During clinical relapse, the parasite was detected by culture in 21 of 24 blood samples and by nested PCR in 23 of 24 blood samples. After treatment and during asymptomatic periods, the parasite was detected by culture in 18 (19.1%) of 94 blood samples and by nested PCR in 58 (61.7%) of 94 blood samples. For positive blood cultures, the Kaplan-Meier probability estimates for relapse at 6, 12, 18, and 24 months were 44%, 68%, 76%, and 76%, respectively, while for positive nested PCRs, the estimates were 20%, 33%, 45%, and 50%, respectively. For negative blood cultures, relapse probabilities for the same time points were 7%, 12%, 12%, and 12%, while for negative nested PCRs, these probabilities were 8%, 14%, 21%, and 26%. Nested PCR-positive results in asymptomatic periods indicated presence of the parasite, but not necessarily relapse. However, the presence of viable parasites during post-treatment follow-up increased the probability of relapse and showed that culture positivity could be a good relapse marker.