We serendipitously discovered that the marine bacterium Vibrio fischeri induces sexual reproduction in one of the closest living relatives of animals, the choanoflagellate Salpingoeca rosetta. Although bacteria influence everything from nutrition and metabolism to cell biology and development in eukaryotes, bacterial regulation of eukaryotic mating was unexpected. Here, we show that a single V. fischeri protein, the previously uncharacterized EroS, fully recapitulates the aphrodisiac-like activity of live V. fischeri. EroS is a chondroitin lyase; although its substrate, chondroitin sulfate, was previously thought to be an animal synapomorphy, we demonstrate that S. rosetta produces chondroitin sulfate and thus extend the ancestry of this important glycosaminoglycan to the premetazoan era. Finally, we show that V. fischeri, purified EroS, and other bacterial chondroitin lyases induce S. rosetta mating at environmentally relevant concentrations, suggesting that bacteria likely regulate choanoflagellate mating in nature.