Natural killer (NK) cells likely play an important role in immunity to malaria, but the effect of repeated malaria on NK cell responses remains unclear. Here, we comprehensively profiled the NK cell response in a cohort of 264 Ugandan children. Repeated malaria exposure was associated with expansion of an atypical, CD56 ^neg population of NK cells that differed transcriptionally, epigenetically, and phenotypically from CD56 ^dim NK cells, including decreased expression of PLZF and the Fc receptor γ-chain, increased histone methylation, and increased protein expression of LAG-3, KIR, and LILRB1. CD56 ^neg NK cells were highly functional and displayed greater antibody-dependent cellular cytotoxicity than CD56 ^dim NK cells. Higher frequencies of CD56 ^neg NK cells were associated with protection against symptomatic malaria and high parasite densities. After marked reductions in malaria transmission, frequencies of these cells rapidly declined, suggesting that continuous exposure to Plasmodium falciparum is required to maintain this modified, adaptive-like NK cell subset.