Vibrio cholerae, the causative agent of the disease cholera, uses a cell to cell communication process called quorum sensing to control biofilm formation and virulence factor production. The major V. cholerae quorum-sensing signal CAI-1 has been identified as (S)-3-hydroxytridecan-4-one, and the CqsA protein is required for CAI-1 production. However, the biosynthetic route to CAI-1 remains unclear. Here we report that (S)-adenosylmethionine (SAM) is one of the two biosynthetic substrates for CqsA. CqsA couples SAM and decanoyl-coenzyme A to produce a previously unknown but potent quorum-sensing molecule, 3-aminotridec-2-en-4-one (Ea-CAI-1). The CqsA mechanism is unique; it combines two enzymatic transformations, a β,γ-elimination of SAM and an acyltransferase reaction into a single PLP-dependent catalytic process. Ea-CAI-1 is subsequently converted to CAI-1, presumably through the intermediate tridecane-3,4-dione (DK-CAI-1). We propose that the Ea-CAI-1 to DK-CAI-1 conversion occurs spontaneously, and we identify the enzyme responsible for the subsequent step: conversion of DK-CAI-1 into CAI-1. SAM is the substrate for the synthesis of at least three different classes of quorum-sensing signal molecules, indicating that bacteria have evolved a strategy to leverage an abundant substrate for multiple signaling purposes.