Background: Early progression of AIDS-associated Kaposi sarcoma (KS-PD) and immune reconstitution inflammatory syndrome (KS-IRIS) sometimes occur after the initiation of antiretroviral therapy (ART). Methods: Early KS-PD and KS-IRIS were assessed in the A5264/AMC-067 trial in which participants with mild-to-moderate AIDS-KS were randomized to initiate ART with either immediate or as-needed oral etoposide. Early KS-PD was defined as tumor progression within 12 weeks of ART initiation. When investigators had concern that early KS-PD was KS-IRIS, additional evaluations were performed. Suspected KS-IRIS was defined as early KS-PD accompanied by a CD4 count increase of ≥50 cells per cubic millimeter or plasma HIV-1 RNA decrease of ≥0.5 log10 copies/mL. Clinical outcome was a composite end point categorized as failure, stable, and response at 48 and 96 weeks compared with baseline. Results: Fifty of 190 participants had early KS-PD (27%): 28 had KS-IRIS and 22 were not evaluated for KS-IRIS. Early KS-PD and KS-IRIS incidences with immediate etoposide versus ART alone were 16% versus 39%, and 7% versus 21%, respectively. Week 48 clinical outcome was 45% failure, 18% stable, and 37% response for no early KS-PD; 82% failure, 2% stable, and 16% response for early KS-PD; and 88% failure, 0% stable, and 12% response for KS-IRIS. Cumulative incidence of KS tumor response by week 96 was 64% for no early KS-PD, 22% with early KS-PD, and 18% with KS-IRIS. Conclusions: Early KS-PD, including suspected KS-IRIS, was common after starting ART for AIDS-KS and was associated with worse long-term clinical outcomes. Starting ART concurrently with etoposide reduced the incidence of both early KS-PD and KS-IRIS compared with ART alone.