Microbial symbioses are essential for the normal development and growth of animals. Often, symbionts must be acquired from the environment during each generation, and identification of the relevant symbiotic partner against a myriad of unwanted relationships is a formidable task. Although examples of this specificity are well-documented, the genetic mechanisms governing it are poorly characterized. Here we show that the two-component sensor kinase RscS is necessary and sufficient for conferring efficient colonization of Euprymna scolopes squid by bioluminescent Vibrio fischeri from the North Pacific Ocean. In the squid symbiont V. fischeri ES114, RscS controls light-organ colonization by inducing the Syp exopolysaccharide, a mediator of biofilm formation during initial infection. A genome-level comparison revealed that rscS, although present in squid symbionts, is absent from the fish symbiont V. fischeri MJ11. We found that heterologous expression of RscS in strain MJ11 conferred the ability to colonize E. scolopes in a manner comparable to that of natural squid isolates. Furthermore, phylogenetic analyses support an important role for rscS in the evolution of the squid symbiosis. Our results demonstrate that a regulatory gene can alter the host range of animal-associated bacteria. We show that, by encoding a regulator and not an effector that interacts directly with the host, a single gene can contribute to the evolution of host specificity by switching 'on' pre-existing capabilities for interaction with animal tissue.