The dinucleotide second messenger c-di-GMP has emerged as a central regulator of reversible cell attachment during bacterial biofilm formation. A prominent cell adhesion mechanism first identified in pseudomonads combines two c-di-GMP-mediated processes: transcription of a large adhesin and its cell surface display via posttranslational proteolytic control. Here, we characterize an orthologous c-di-GMP effector system and show that it is operational in Vibrio cholerae, where it regulates two distinct classes of adhesins. Through structural analyses, we reveal a conserved autoinhibition mechanism of the c-di-GMP receptor that controls adhesin proteolysis and present a structure of a c-di-GMP-bound receptor module. We further establish functionality of the periplasmic protease controlled by the receptor against the two adhesins. Finally, transcription and functional assays identify physiological roles of both c-di-GMP-regulated adhesins in surface attachment and biofilm formation. Together, our studies highlight the conservation of a highly efficient signaling effector circuit for the control of cell surface adhesin expression and its versatility by revealing strain-specific variations.IMPORTANCEVibrio cholerae, the causative agent of the diarrheal disease cholera, benefits from a sessile biofilm lifestyle that enhances survival outside the host but also contributes to host colonization and infectivity. The bacterial second messenger c-di-GMP has been identified as a central regulator of biofilm formation, including in V. cholerae; however, our understanding of the pathways that contribute to this process is incomplete. Here, we define a conserved signaling system that controls the stability of large adhesion proteins at the cell surface of V. cholerae, which are important for cell attachment and biofilm formation. Insight into the regulatory circuit underlying biofilm formation may inform targeted strategies to interfere with a process that renders this bacterium remarkably adaptable to changing environments.