Abstract: This study focus on the phylogenetic relationships among six Proto-Malay tribes (Jakun, Temuan, Semelai, Kuala, Seletar and Kanaq) and the effectiveness of using HVSI D-loop region segment and a 9 bp deletion of the intergenic region of COII/tRNALys of mtDNA in portraying the phylogenetic relationships. The analysis showed high pairwise differences among Kanaq, Jakun and Semelai. Thirty two haplotypes were formed from 89 D-loop sequences of Proto Malay individuals. Deletion on the 9 bp tandem repeats of COII/tRNALys was detected in Semelai and Orang Kuala. Neighbor-Joining, Maximum Parsimony and Maximum Likelihood analysis revealed Jakun and Semelai haplotypes are the earliest to split from ingroups and showed that Jakun may be an ancestor for the Malay populations in the Malay Peninsular, which also support the anthropological findings. Nine basepair deletion of COII/tRNALys intergenic region had occurred in two clades. Results indicates a close relationships among Semelai, Temuan and Jakun. Most Kanaq and Seletar sequences were merged into tribe specific haplotypes, showing close relationships within tribes. The HVS I D-loop region of most Proto Malays are highly variable as 27 of 32 haplotypes were subgroup-specific. The HVS I of D-loop successfully revealed the close relationships among the Proto-Malays but was less effective in discriminating each tribe. Detection of ancestries for the Proto Malays using 9 bp deletion of COII/tRNALys intergenic region reveals the Asian origins for Kuala and Semelai.