APOE4 is the strongest genetic risk factor for Alzheimer’s disease1-3. However, the effects of APOE4 on the human brain are not fully understood, limiting opportunities to develop targeted therapeutics for individuals carrying APOE4 and other risk factors for Alzheimer’s disease4-8. Here, to gain more comprehensive insights into the impact of APOE4 on the human brain, we performed single-cell transcriptomics profiling of post-mortem human brains from APOE4 carriers compared with non-carriers. This revealed that APOE4 is associated with widespread gene expression changes across all cell types of the human brain. Consistent with the biological function of APOE2-6, APOE4 significantly altered signalling pathways associated with cholesterol homeostasis and transport. Confirming these findings with histological and lipidomic analysis of the post-mortem human brain, induced pluripotent stem-cell-derived cells and targeted-replacement mice, we show that cholesterol is aberrantly deposited in oligodendrocytes-myelinating cells that are responsible for insulating and promoting the electrical activity of neurons. We show that altered cholesterol localization in the APOE4 brain coincides with reduced myelination. Pharmacologically facilitating cholesterol transport increases axonal myelination and improves learning and memory in APOE4 mice. We provide a single-cell atlas describing the transcriptional effects of APOE4 on the aging human brain and establish a functional link between APOE4, cholesterol, myelination and memory, offering therapeutic opportunities for Alzheimer’s disease.