Background. Human-Immunodeficiency-Virus- (HIV-) related Kaposi's sarcoma (KS) has a high prevalence in Africa; however, there is minimal published data on treatment and outcomes in this population. Objective and Design. This was a prospective study of 50 patients, aiming to assess the impact of vincristine therapy on tumour response and survival and to assess palliative care outcomes in patients with HIV-related KS. Methods. 50 consecutive patients were recruited during 2008. Vincristine therapy and highly active antiretroviral therapy (HAART) were given. Tumour response, survival, and chemotherapy-related toxicities were documented. Palliative care outcomes were assessed using the African Palliative Care Association (APCA) Palliative Outcome Scale (POS). Results. The majority of patients were male, and the median age was 33 years. At baseline assessment, the median CD4 T-cell count was 263, and 50% patients had evidence of peripheral neuropathy. The overall response rate was 64% at 6 weeks, and median progression-free survival was 30 weeks. Treatment was generally well tolerated, with peripheral neuropathy the main dose-limiting toxicity. Conclusion. The combination of vincristine and HAART is feasible and effective in a low resource setting, although peripheral neuropathy is a dose-limiting factor. This patient group carries a high mortality and as such adequate access to palliative care is crucial.