Sexual selection can directly contribute to reproductive isolation and is an important mechanism that can lead to speciation. Lek-mating is one of the most extreme forms of sexual selection, but surprisingly does not seem to preclude occasional hybridization in nature. However, hybridization among lekking species may still be trivial if selection against offspring with intermediate phenotypes prohibits introgression. Here we investigate this further by sequencing the genomes of nearly all bird-of-paradise (Paradisaeidae) species and 10 museum specimens of putative hybrid origin. We find that intergeneric hybridization indeed still takes place despite extreme differentiation in form, plumage, and behavior. In parallel, the genomes of contemporary species contain widespread signatures of past introgression, demonstrating that hybridization has repeatedly resulted in shared genetic variation despite strong sexual isolation. Our study raises important questions about extrinsic factors that modulate hybridization probability and the evolutionary consequences of introgressive hybridization between lekking species.