East Timor is a country which harbors multiple ethnolinguistic groups generally assigned to an Austronesian or Papuan ancestry. The present study aimed to characterize Y-chromosome haplotype diversity in East Timor, and to test possible population structures based on linguistic and/or geographical information. Using a set of 12 Y-chromosome-specific STRs (DYS19, DYS389I and II, DYS390, DYS391, DYS392, DYS393, DYS385, DYS437, DYS438, and DYS439), haplotypes were established in 342 individuals from 12 linguistic groups (Tetum, Kwaimina, Galoli, Wetarese, Dawan, Mambai, Kemak, Tokodede, Bunak, Makasai, Makalero, and Fataluku) belonging to the three major ethnolinguistic groups in East Timor: two from the Timorese-Austronesian branch (Fabronic and Ramelaic), and a third including languages related to a Trans-New Guinea phylum (Papuan). High values of haplotype diversity, average gene diversity, and mean number of pairwise differences per locus were found in all 12 linguistic groups, except for the Wetarese from the island of Ataúro. Analysis of genetic variance (AMOVA) and pairwise genetic distance analysis showed that the East Timor population is genetically structured, and if the Bunak and Wetarese are excluded, samples group well with respect to their language affinities, and furthermore, the most genetically homogeneous groups are those following the broad ethnolinguistic classifications. Bunak and Wetarese behave as outsider groups, and are genetically more closely related to populations classified in a different linguistic group.