Hybridisation is known to occur between a wide range of taxa, including species for which strong sexual selection has led to markedly different sexual phenotypes and lek-mating behaviours. To what extent occasional hybridisation can overcome the reproductive barriers in such systems and, for example, lead to the establishment of hybrid zones is poorly known. In this study, we address this question by focusing on one of the most well-known avian radiations in which sexual selection has resulted in an extraordinary assemblage of phenotypic diversity and lek-mating behaviours: the birds-of-paradise (Paradisaeidae). We quantify the genome-wide distribution of introgression and find multiple signals of recent and historical gene flow between and within two genera of birds-of-paradise, Astrapia and Paradigalla. In addition, we present the first empirical genomic indication of a putative hybrid zone between two lekking bird-of-paradise species that differ substantially in their sexually selected traits and behaviours. Our findings are consistent with the idea that behavioural and phenotypic traits may constitute weaker pre- and post-zygotic barriers to gene flow than generally thought in lek-mating species.