The Malays and their many sub-ethnic groups collectively make up one of the largest population groups in Southeast Asia. However, their genomes, especially those from Brunei, remain very much underrepresented and understudied. Here, we analysed the publicly available WGS and genotyping data of two and 39 Bruneian Malay individuals, respectively. NGS reads from the two individuals were first mapped against the GRCh38 human reference genome and their variants called. Of the total ∼5.28 million short nucleotide variants and indels identified, ∼217K of them were found to be novel; with some predicted to be deleterious and associated with risk factors of common non-communicable diseases in Brunei. Unmapped reads were next mapped against the recently reported novel Chinese and Japanese genomic contigs and de novo assembled. ∼227 Kbp genomic sequences missing in GRCh38 and a partial open reading frame encoding a potential novel small zinc finger protein were successfully discovered. Interestingly, although the Malays in Brunei, Singapore and Malaysia share >83% common variants, principal component and admixture analysis comparing the genetic structure of the local Malays against other Asian population groups suggested that they are genetically closer to some Filipino ethnic groups than the Malays in Malaysia and Singapore. Taken together, our work provides the first comprehensive insight into the genomes of the Bruneian Malay population.