Instances of parallel phenotypic evolution offer great opportunities to understand the evolutionary processes underlying phenotypic changes. However, confirming parallel phenotypic evolution and studying its causes requires a robust phylogenetic framework. One such example is the “black-and-white wagtails”, a group of five species in the songbird genus Motacilla: one species, the White Wagtail (M. alba), shows wide intra-specific plumage variation, while the four others form two pairs of very similar-looking species (African Pied Wagtail M. aguimp + Mekong Wagtail M. samveasnae and Japanese Wagtail M. grandis + White-browed Wagtail M. maderaspatensis, respectively). However, the two species in each of these pairs were not recovered as sisters in previous phylogenetic inferences. Their relationships varied depending on the markers used, suggesting that gene tree heterogeneity might have hampered accurate phylogenetic inference. Here, we use whole genome resequencing data to explore the phylogenetic relationships within this group, with a special emphasis on characterizing the extent of gene tree heterogeneity and its underlying causes. We first used multispecies coalescent methods to generate a “complete evidence” phylogenetic hypothesis based on genome-wide variants, while accounting for incomplete lineage sorting and introgression. We then investigated the variation in phylogenetic signal across the genome, to quantify the extent of discordance across genomic regions, and test its underlying causes. We found that wagtail genomes are mosaics of regions supporting variable genealogies, because of ILS and inter-specific introgression. The most common topology across the genome, supporting M. alba and M. aguimp as sister species, appears to be influenced by ancient introgression. Additionally, we inferred another ancient introgression event, between M. alba and M. grandis. By combining results from multiple analyses, we propose a phylogenetic network for the black-and-white wagtails that confirms that similar phenotypes evolved in non-sister lineages, supporting parallel plumage evolution. Furthermore, the inferred reticulations do not connect species with similar plumage coloration, suggesting that introgression does not underlie parallel plumage evolution in this group. Our results demonstrate the importance of investigation of genome-wide patterns of gene tree heterogeneity to help understanding the mechanisms underlying phenotypic evolution.