Summary Background Literature on cancer in adolescents and young adults (AYA; aged 15–24 years) living with HIV is scarce. We studied cancer incidence in AYA living with HIV in South Africa between 2004 and 2014. Methods In this nationwide cohort study, we included individuals between 15 and 24 years old who had at least two HIV-related laboratory measurements on separate days between Jan 1, 2004, and Dec 31, 2014, recorded in the National Health Laboratory Service database. We used privacy-preserving probabilistic record linkage methods to identify HIV-related laboratory records that most likely belonged to the same individual and to then link these individuals to cancer diagnoses from the National Cancer Registry. We computed incidence rates for the most common cancers in AYA living with HIV, and we assessed associations between these cancers and sex, age, calendar year, and CD4 cell count using Cox proportional hazards models and adjusted hazard ratios (aHRs). Findings We included 782 454 AYA living with HIV (698 066 [89·2%] women) with 1 428 114 person-years of follow-up. Of those, 867 developed incident cancer (incidence rate 60·7 per 100 000 person-years), including 429 who developed Kaposi sarcoma (30·0 per 100 000 person-years), 107 non-Hodgkin lymphoma (7·5 per 100 000 person-years), 48 Hodgkin lymphoma (3·4 per 100 000 person-years), 45 cervical cancer (3·4 per 100 000 woman-years), and 32 leukaemia (2·2 per 100 000 person-years). Kaposi sarcoma was more common in the 20–24 year age group than the 15–19 year age group (aHR 1·39, 95% CI 1·03–1·86). Male sex was associated with higher rates of Kaposi sarcoma (2·06, 1·61–2·63), non-Hodgkin lymphoma (3·17, 2·06–4·89), Hodgkin lymphoma (4·83, 2·61–8·93), and leukaemia (unadjusted HR 5·90, 95% CI 2·87–12·12). Cancer rates decreased over the study period, driven by declining Kaposi sarcoma rates. Lower baseline CD4 cell counts were associated with higher rates of Kaposi sarcoma, cervical cancer, non-Hodgkin lymphoma, and Hodgkin lymphoma, but not leukaemia. Interpretation Infection-related cancers were the most common cancer types in AYA living with HIV in South Africa, and their incidence rates increased with lower CD4 cell counts. Therefore, innovative strategies to maintaining high CD4 cell counts are needed to reduce the cancer burden in this vulnerable population. Funding US National Institutes of Health and Swiss National Science Foundation.