Bacteria have developed multiple strategies to adapt to diverse ecological niches and hostile environments. One such strategy involves formation and maintenance of multicellular communities known as biofilms. In these microbial aggregates, sessile bacterial cells are encased in an extracellular matrix. It has now been established that c-di-GMP, a ubiquitous bacterial second messenger, is a central regulator of this developmental process in bacteria. It exerts its effects on transcriptional, translational and post-translational levels. While diguanylate cyclases and phosphodiesterases with conserved GGDEF and EAL (and HD-GYP) domains are responsible for the production and degradation of the dinucleotide, respectively, the receptors form a more diverse group with degenerate, catalytically inactive GGDEFEAL domain-containing proteins representing a major subfamily. One such protein, LapD from Pseudomonas fluorescens, uses an inside-out signaling mechanism to relay intracellular c-di-GMP concentration to control the localization of an outer-membrane anchored large adhesin protein LapA at the cell surface, by sequestering a periplasmic cysteine protease, LapG. When free, LapG cleaves the N-terminus of LapA, releasing it from the cell surface and ultimately leading to biofilm dispersal. Based on our structure-function analysis, here we propose a mechanism for the c-di-GMP-mediated, regulation of periplasmic proteolysis by LapD. We first elucidate the molecular basis of signal recognition and relay by P. fluorescens LapD and identify orthologous systems in multiple other bacteria including many pathogens such as Legionella pneumophila. This is followed by our work on L. pneumophila LapG, which provides us with the first atomic models of a bacterial protease of the DUF920 family and we are able to identify a highly conserved Ca2+-binding motif integral to its function. We then characterize the LapD-ortholog CdgS9 from L. pneumophila which confirms a common molecular mechanism. The crystal structure of the periplasmic output domain module reveals novel conformations and sheds new light on the mode of activation of the receptor. We finally report the structure of a complex between CdgS9output and P. fluorescens LapG which led to the discovery of the pharmacologically relevant binding interface between the output domain and LapG.