Perinatally-acquired HIV has persistent effects on long-term health outcomes, even after early treatment. We hypothesize that epigenetic indicators, such as DNA methylation, may elucidate cellular processes that explain these effects. Here, we compared DNA methylation profiles in whole blood from 120 HIV-infected children on antiretroviral therapy (ART) and 60 frequency age-matched HIV-uninfected children aged 4–9 years in Johannesburg, South Africa. Using an individual CpG site approach, we found 1,309 differentially-methylated (DM) CpG sites between groups, including 1,271 CpG sites that were hyper-methylated in the HIV-infected group and 38 CpG sites that were hypo-methylated in the HIV-infected group. Six hyper-methylated CpG sites were in EBF4, which codes for a transcription factor involved in B-cell maturation. The top hypomethylated site was in the promoter region of NLRC5, encoding a transcription factor that regulates major histocompatibility complex (MHC) class I molecule expression. Using a differentially-methylated region (DMR) approach, we found 315 DMRs between groups, including 28 regions encompassing 686 CpG sites on chromosome 6. A large number of the genes identified in both the CpG site and DMR approaches were located in the MHC region on chromosome 6, which plays an important role in the adaptive immune system. This study provides the first evidence that changes in the epigenome are detectable in children with perinatally-acquired HIV infection on suppressive ART started at an early age.