Novel organismal structures in metazoans are often undergirded by complex gene regulatory networks; as such, understanding the emergence of new structures through evolution requires reconstructing the series of evolutionary steps leading to these underlying networks. Here, we reconstruct the step-by-step assembly of the vertebrate splicing network regulated by Nova , a splicing factor that modulates alternative splicing in the vertebrate central nervous system by binding to clusters of YCAY motifs on pre-RNA transcripts. Transfection of human HEK293T cells with Nova orthologs indicated vertebrate-like splicing regulatory activity in bilaterian invertebrates, thus Nova acquired the ability to bind YCAY clusters and perform vertebrate-like splicing modulation at least before the last common ancestor of bilaterians. In situ hybridization studies in several species showed that Nova expression became restricted to CNS later on, during chordate evolution. Finally, comparative genomics studies revealed a diverse history for Nova -regulated exons, with target exons arising through both de novo exon creation and acquisition of YCAY motifs by preexisting exons throughout chordate and vertebrate history. In addition, we find that tissue-specific Nova expression patterns emerged independently in other lineages, suggesting independent assembly of tissue-specific regulatory networks.