BACKGROUND: Throughout most of sub-Saharan Africa (and, indeed, most resource-limited areas), lack of death registries prohibits linkage of cancer diagnoses and precludes the most expeditious approach to determining cancer survival. Instead, estimation of cancer survival often uses clinical records, which have some mortality data but are replete with patients who are lost to follow-up (LTFU), some of which may be caused by undocumented death. The end result is that accurate estimation of cancer survival is rarely performed. A prominent example of a common cancer in Africa for which survival data are needed but for which frequent LTFU has precluded accurate estimation is Kaposi sarcoma (KS). METHODS: Using electronic records, we identified all newly diagnosed KS among HIV-infected adults at 33 primary care clinics in Kenya, Uganda, Nigeria, and Malawi from 2009 to 2012. We determined those patients who were apparently LTFU, defined as absent from clinic for ≥90 days at database closure and unknown to be dead or transferred. Using standardized protocols which included manual chart review, telephone calls, and physical tracking in the community, we attempted to update vital status amongst patients who were LTFU. RESULTS: We identified 1222 patients with KS, of whom 440 were LTFU according to electronic records. Manual chart review revealed that 18 (4.1%) were classified as LFTU due to clerical error, leaving 422 as truly LTFU. Of these 422, we updated vital status in 78%; manual chart review was responsible for updating in 5.7%, telephone calls in 26%, and physical tracking in 46%. Among 378 patients who consented at clinic enrollment to be tracked if they became LTFU and who had sufficient geographic contact/locator information, we updated vital status in 88%. Duration of LTFU was not associated with success of tracking, but tracking success was better in Kenya than the other sites. CONCLUSION: It is feasible to update vital status in a large fraction of patients with HIV-associated KS in sub-Saharan Africa who have become LTFU from clinical care. This finding likely applies to other cancers as well. Updating vital status amongst lost patients paves the way towards accurate determination of cancer survival.