Genetic variation in host immunity impacts the disproportionate burden of infectious diseases that can be experienced by First Nations peoples. Polymorphic human leukocyte antigen (HLA) class I and killer cell immunoglobulin-like receptors (KIRs) are key regulators of natural killer (NK) cells, which mediate early infection control. How this variation impacts their responses across populations is unclear. We show that HLA-A24:02 became the dominant ligand for inhibitory KIR3DL1 in First Nations peoples across Oceania, through positive natural selection. We identify KIR3DL1114, widespread across and unique to Oceania, as an allele lineage derived from archaic humans. KIR3DL1114NK cells from First Nations Australian donors are inhibited through binding HLA-A24:02. The KIR3DL1114 lineage is defined by phenylalanine at residue 166. Structural and binding studies show phenylalanine 166 forms multiple unique contacts with HLA-peptide complexes, increasing both affinity and specificity. Accordingly, assessing immunogenetic variation and the functional implications for immunity are fundamental toward understanding population-based disease associations.