The repeatability or predictability of evolution is a central question in evolutionary biology and most often addressed in experimental evolution studies. Here, we infer how genetically heterogeneous natural systems acquire the same molecular changes to address how genomic background affects adaptation in natural populations. In particular, we take advantage of independently formed neo-sex chromosomes in Drosophila species that have evolved dosage compensation by co-opting the dosage-compensation male-specific lethal (MSL) complex to study the mutational paths that have led to the acquisition of hundreds of novel binding sites for the MSL complex in different species. This complex recognizes a conserved 21-bp GA-rich sequence motif that is enriched on the X chromosome, and newly formed X chromosomes recruit the MSL complex by de novo acquisition of this binding motif. We identify recently formed sex chromosomes in the D. melanica and D. robusta species groups by genome sequencing and generate genomic occupancy maps of the MSL complex to infer the location of novel binding sites. We find that diverse mutational paths were utilized in each species to evolve hundreds of de novo binding motifs along the neo-X, including expansions of microsatellites and transposable element (TE) insertions. However, the propensity to utilize a particular mutational path differs between independently formed X chromosomes and appears to be contingent on genomic properties of that species, such as simple repeat or TE density. This establishes the "genomic environment" as an important determinant in predicting the outcome of evolutionary adaptations.