Background: Optimal treatment regimens for AIDS-associated Kaposi sarcoma, a frequent contributor to morbidity and mortality among people with HIV, have not been systematically evaluated in low-income and middle-income countries, where the disease is most common. In this study, we aimed to investigate optimal treatment strategies for advanced stage disease in areas of high prevalence and limited resources. Methods: In this open-label, non-inferiority trial, we enrolled people with HIV and advanced stage AIDS-associated Kaposi sarcoma attending 11 AIDS Clinical Trials Group sites in Brazil, Kenya, Malawi, South Africa, Uganda, and Zimbabwe. Eligible participants were randomly assigned (1:1:1) with a centralised computer system to receive either intravenous bleomycin and vincristine or oral etoposide (the investigational arms), or intravenous paclitaxel (the control arm), together with antiretroviral therapy (ART; combined efavirenz, tenofovir disoproxil fumarate, and emtricitabine). The primary outcome was progression-free survival (PFS) at week 48, using a 15% non-inferiority margin to compare the investigational groups against the active control group. Safety was assessed in all eligible treated study participants. The study was registered with ClinicalTrials.gov, NCT01435018. Findings: 334 participants were enrolled between Oct 1, 2013, and March 8, 2018, when the study was closed early due to inferiority of the bleomycin and vincristine plus ART arm, as per the recommendations of the Data and Safety Monitoring Board (DSMB). The etoposide plus ART arm also closed due to inferiority in March, 2016, following a DSMB recommendation. Week-48 PFS rates were higher in the paclitaxel plus ART arm than in both investigational arms. The absolute differences in PFS were –30% (95% CI –52 to –8) for the comparison of paclitaxel plus ART (week 48 PFS 50%, 32 to 67; n=59) and etoposide plus ART (20%, 6 to 33; n=59), and –20% (–33% to –7%) for the comparison of paclitaxel plus ART (64%, 55 to 73; n=138) and bleomycin and vincristine plus ART (44%, 35 to 53; n=132). Both CIs overlapped the non-inferiority margin. The most common adverse events, in 329 eligible participants who began treatment, were neutropenia (48 [15%]), low serum albumin (33 [10%]), weight loss (29 [9%]), and anaemia (28 [9%]), occurring at similar frequency across treatment arms. Interpretation Non-inferiority of either investigational intervention was not shown, with paclitaxel plus ART showing superiority to both oral etoposide plus ART and bleomycin and vincristine plus ART, supporting its use in treating advanced AIDS-associated Kaposi sarcoma in resource-limited settings. Funding: US National Institute of Allergy and Infectious Diseases and National Cancer Institute, National Institutes of Health.