The European Gypsies, commonly referred to as Roma, are represented by a vast number of groups spread across many countries. Although sharing a common origin, the Gypsy groups are highly heterogeneous as a consequence of genetic drift and different levels of admixture with surrounding populations. With this study we aimed at contributing to the knowledge of the Roma history by studying 17 Y-STR and 34 Y-SNP loci in a sample of 126 Portuguese Gypsies. Distinct genetic hallmarks of their past and migration route were detected, namely: an ancestral component, shared by all Roma groups, that reflects their origin in India (H1a-M82; approximately 17%); an influence from their long permanence in the Balkans/Middle-East region (J2a1b-M67, J2a1b1-M92, I-M170, Q-M242; approximately 31%); traces of contacts with European populations preceding the entrance in the Iberian Peninsula (R1b1c-M269, J2b1a-M241; approximately 10%); and a high proportion of admixture with the non-Gypsy population from Iberia (R1b1c-M269, R1-M173/del.M269, J2a-M410, I1b1b-M26, E3b1b-M81; approximately 37%). Among the Portuguese Gypsies the proportion of introgression from host populations is higher than observed in other groups, a fact which is somewhat unexpected since the arrival of the Roma to Portugal is documented to be more recent than in Central or East Europe.