The sub-Himalayan Terai and Duars, the important outermost zones comprising the plains of East India, are known as the reservoirs of ethnic diversity. Analysis of the paternal genetic diversity of the populations inhabiting these regions and their genetic relationships with adjacent Himalayan and other Asian populations has not been addressed empirically. In the present investigation, we undertook a Y-chromosome phylogeographic study on 10 populations (n=375) representing four different linguistic groups from the sub-Himalayan Terai and Duars regions of East India. The high-resolution analysis of Y-chromosome haplogroup variations based on 76 binary markers revealed that the sub-Himalayan paternal gene pool is extremely heterogeneous. Three major haplogroups, namely H, O and R, are shared across the four linguistic groups. The Indo-European-speaking castes exhibit more haplogroup diversity than the tribal groups. The findings of the present investigation suggest that the sub-Himalayan gene pools have received predominant Southeast Asian contribution. In addition, the presence of Northeast and South Asian signatures illustrate multiple events of population migrations as well as extensive genetic admixture amongst the linguistic groups.