Natural Killer (NK) cells likely play an important role in immunity to malaria, but whether repeated malaria modifies the NK cell response 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, CD56neg population of NK cells that differed transcriptionally, epigenetically, and phenotypically from CD56dim NK cells, including decreased expression of PLZF and the Fc receptor g chain, increased histone methylation, and increased protein expression of LAG-3, KIR and LILRB1. CD56neg NK cells were highly functional, displaying greater antibody dependent cellular cytotoxicity than CD56dim NK cells, and higher frequencies of these cells were associated with protection against symptomatic malaria and high parasite densities. Importantly, following marked reductions in malaria transmission, frequencies of these cells rapidly declined, suggesting that continuous exposure to malaria is required to maintain this modified, adaptive-like NK cell subset.