In this study, 123 unrelated Portuguese Gypsies were analyzed for 15 highly polymorphic autosomal short tandem repeats (STRs). Average gene diversity across the 15 markers was 76.7%, which is lower than that observed in the non-Gypsy Portuguese population. Subsets of STRs were used to perform comparisons with other Gypsy and corresponding host populations. Interestingly, diversity reduction in Gypsy groups compared to their non-Gypsy surrounding populations apparently varied according to an East-West gradient, which parallels their dispersion in Europe as well as a decrease in complexity of their internal structure. Analysis of genetic distances revealed that the average level of genetic differentiation between Gypsy groups was much larger than that observed between the corresponding non-Gypsy populations. The high rate of heterogeneity among Gypsies can be explained by strong genetic drift and limited intergroup gene flow. However, when genetic relationships were addressed through principal component analysis, all Gypsy populations clustered together and was clearly distinguished from other populations, a pattern that suggests their common origin. Concerning the putative ancestral genetic component, admixture analysis did not reveal strong Indian ancestry in the current Gypsy gene pools, in contrast to the high admixture estimates for either Europeans or Western Asians.