A major goal in biology is to understand how organisms evolve novel traits. Multiple studies have identified genes contributing to regressive evolution, the loss of structures that existed in a recent ancestor. However, fewer examples exist for genes underlying constructive evolution, the gain of novel structures and capabilities in lineages that previously lacked them. Sea robins are fish that have evolved enlarged pectoral fins, six mobile locomotory fin rays (legs) and six novel macroscopic lobes in the central nervous system (CNS) that innervate the corresponding legs. Here, we establish successful husbandry and use a combination of transcriptomics, CRISPR-Cas9 editing, and behavioral assays to identify key transcription factors that are required for leg formation and function in sea robins. We also generate hybrids between two sea robin species with distinct leg morphologies and use allele-specific expression analysis and gene editing to explore the genetic basis of species-specific trait diversity, including a novel sensory gain of function. Collectively, our study establishes sea robins as a new model for studying the genetic basis of novel organ formation, and demonstrates a crucial role for the conserved limb gene tbx3a in the evolution of chemosensory legs in walking fish.