Sex-determination relies on the proper control of a hierarchically structured multilayered network of genes. The genes at the top orchestrate complex transcriptional and post-transcriptional regulations. Despite such critical function they appear to be dispensable in evolutionary terms and can be quickly replaced with the emergence of new lineages. Our analysis shows that concomitantly to the acquisition of a dominant position within the sex-determining network, the medaka master male determiner dmrt1bY was subjected to a profound rearrangement of its regulatory landscape. Requiring a complete rewiring of the regulatory network, this evolutionary innovation was partly brought about by exaptation of a “ready-to-use” pre-existing cis-regulatory element contributed by a transposable element (TE), called Izanagi. This element acts as a silencer, which recruits both proteins Dmrt1bY and Dmrt1a to turn-off the dmrt1bY gene after it has fulfilled its function as the primary male SD gene. Exceeding this simple feedback regulation we now report that TE-mediated transcriptional rewiring can reach an unexpected level of complexity. We find that another TE, Rex1, has jumped into Izanagi. Through disruption of Izanagi, Rex1 immobilized this TE and fixed the Dmrt1-mediated down-regulation. Moreover, Rex1 brought in a preformed regulatory element for Sox5, which critically functions in establishing the temporal and cell-type specific expression pattern of dmrt1bY. Although Sox5 has not been implicated in sex-determination previously we show its critical involvement in medaka male development through regulation of primordial germ cell numbers. Disruption of sox5 leads to XX female-to-male sex-reversal, underpinning the importance of the Rex1 TE for the establishment of a new sex-determining mechanism in medaka.