Immigrants from diverse origins have arrived in Paraguay and produced important demographic changes in a territory initially inhabited by indigenous Guarani. Few studies have been performed to estimate the proportion of Native ancestry that is still preserved in Paraguay and the role of females and males in admixture processes. Therefore, 548 individuals from eastern Paraguay were genotyped for three marker sets: mtDNA, Y-SNPs and autosomal AIM-InDels. A genetic homogeneity was found between departments for each set of markers, supported by the demographic data collected, which showed that only 43% of the individuals have the same birthplace as their parents. The results show a sex-biased intermarriage, with higher maternal than paternal Native American ancestry. Within the native mtDNA lineages in Paraguay (87.2% of the total), most haplogroups have a broad distribution across the subcontinent, and only few are concentrated around the Paraná River basin. The frequency distribution of the European paternal lineages in Paraguay (92.2% of the total) showed a major contribution from the Iberian region. In addition to the remaining legacy of the colonial period, the joint analysis of the different types of markers included in this study revealed the impact of post-war migrations on the current genetic background of Paraguay.