The heterogenous population of Malaysia includes more than 50 indigenous groups, and characterizing their HLA diversity would not only provide insights to their ancestry, but also on the effects of natural selection on their genome. We utilized hybridization-based sequence capture and short-read sequencing on the HLA region of 172 individuals representing seven indigenous groups in Malaysia (Jehai, Kintaq, Temiar, Mah Meri, Seletar, Temuan, Bidayuh). Allele and haplotype frequencies of HLA-A, -B, -C, -DRB1, -DQA1, -DQB1, -DPA1, and -DPB1 revealed several ancestry-informative markers. Using SNP-based heterozygosity and pairwise Fst, we observed signals of natural selection, particularly in HLA-A, -C and -DPB1 genes. Consequently, we showed the impact of natural selection on phylogenetic inference using HLA and non-HLA SNPs. We demonstrate the utility of Next Generation Sequencing for generating unambiguous, high-throughput, high-resolution HLA data that adds to our knowledge of HLA diversity and natural selection in indigenous minority groups.