The Crc protein is a global regulator that has a key role in catabolite repression and optimization of metabolism inPseudomonads. Crc inhibits gene expression post-transcriptionally, preventing translation of mRNAs bearing an AAnAAnAA motif [the catabolite activity (CA) motif] close to the translation start site. Although Crc was initially believed to bind RNA by itself, this idea was recently challenged by results suggesting that a protein co-purifying with Crc, presumably the Hfq protein, could account for the detected RNA-binding activity. Hfq is an abundant protein that has a central role in post-transcriptional gene regulation. Herein, we show that thePseudomonas putidaHfq protein can recognize the CA motifs of RNAs through its distal face and that Crc facilitates formation of a more stable complex at these targets. Crc was unable to bind RNA in the absence of Hfq. However, pull-down assays showed that Crc and Hfq can form a co-complex with RNA containing a CA motifin vitro. Inactivation of thehfqor thecrcgene impaired catabolite repression to a similar extent. We propose that Crc and Hfq cooperate in catabolite repression, probably through forming a stable co-complex with RNAs containing CA motifs to result in inhibition of translation initiation.