Approximately 91% of the world’s children living with HIV (CLWH) are in sub-Saharan Africa (SSA). Living with HIV confers a risk of developing HIV-associated cancers. To determine the incidence and risk factors for cancer among CLWH, we conducted a nested case-control study of children 0–18 years from 2004–2014 at five centers in four SSA countries. Incident cases of cancer and HIV were frequency-matched to controls with HIV and no cancer. We calculated the incidence density by cancer type, logistic regression, and relative risk to evaluate risk factors of cancer. The adjusted incidence density of all cancers, Kaposi sarcoma, and lymphoma were 47.6, 36.6, and 8.94 per 100,000 person-years, respectively. Delayed ART until after 2 years of age was associated with cancer (OR = 2.71, 95% CI 1.51, 4.89) even after adjusting for World Health Organization clinical stage at the time of enrolment for HIV care (OR = 2.85, 95% CI 1.57, 5.13). The relative risk of cancer associated with severe CD4 suppression was 6.19 (p = 0.0002), 2.33 (p = 0.0042), and 1.77 (p = 0.0305) at 1, 5, and 10 years of ART, respectively. The study demonstrates the high risk of cancers in CLWH and the potential benefit of reducing this risk by the early initiation of ART.