Quorum sensing (QS) is a communication mechanism exploited by a large variety of bacteria to coordinate gene expression at the population level. In Gram-negative bacteria, QS occurs via synthesis and detection of small chemical signals, most of which belong to the acyl-homoserine lactone class. In such a system, binding of an acyl-homoserine lactone signal to its cognate transcriptional regulator (R-protein) often induces stabilization and subsequent dimerization of the R-protein, which results in the regulation of downstream gene expression. Existence of diverse QS systems within and among species of bacteria indicates that each bacterium needs to distinguish among a myriad of structurally similar chemical signals. We show, using a mathematical model, that fast degradation of an R-protein monomer can facilitate discrimination of signals that differentially stabilize it. Furthermore, our results suggest an inverse correlation between the stability of an R-protein and the achievable limits of fidelity in signal discrimination. In particular, an unstable R-protein tends to be more specific to its cognate signal, whereas a stable R-protein tends to be more promiscuous. These predictions are consistent with experimental data on well-studied natural and engineered R-proteins and thus have implications for understanding the functional design of QS systems.