In the metabolically versatile bacterium Pseudomonas aeruginosa, the RNA-binding protein Crc is involved in catabolite repression of a range of degradative genes, such as amiE (encoding aliphatic amidase). We found that a CA-rich sequence (termed CA motif) in the amiE translation initiation region was important for Crc binding. The small RNA CrcZ (407 nt) containing 5 CA motifs was able to bind the Crc protein with high affinity and to remove it from amiE mRNA in vitro. Overexpression of crcZ relieved catabolite repression in vivo, whereas a crcZ mutation pleiotropically prevented the utilization of several carbon sources. The sigma factor RpoN and the CbrA/CbrB two-component system, which is known to maintain a healthy carbon-nitrogen balance, were necessary for crcZ expression. During growth on succinate, a preferred carbon source, CrcZ expression was low, resulting in catabolite repression of amiE and other genes under Crc control. By contrast, during growth on mannitol, a poor carbon source, elevated CrcZ levels correlated with relief of catabolite repression. During growth on glucose, an intermediate carbon source, CrcZ levels and amiE expression were intermediate between those observed in succinate and mannitol media. Thus, the CbrA-CbrB-CrcZ-Crc system allows the bacterium to adapt differentially to various carbon sources. This cascade also regulated the expression of the xylS (benR) gene, which encodes a transcriptional regulator involved in benzoate degradation, in an analogous way, confirming this cascade's global role.