In Escherichia coli, the glycolytic enzyme enolase is a component of the RNA degradosome, which is an RNase E mediated assembly involved in RNA processing and transcript turnover. The recruitment of enolase by the RNA degradosome has been implicated in the turnover of certain transcripts, and it is mediated by a small segment of roughly a dozen residues that lie within a natively unstructured sub-domain of RNase E. Here, we present the crystal structure of enolase in complex with its recognition site from RNase E at 1.6A resolution. A single molecule of the RNase E peptide binds asymmetrically in a conserved cleft at the interface of the enolase dimer. The recognition site is well conserved in RNase E homologues in a subfamily of the gamma-proteobacteria, including enzymes from pathogens such as Yersinia pestis, Vibrio cholera and Salmonella sp. We suggest that enolase is recruited into putative RNA degradosome machinery in these bacilli, where it plays common regulatory functions.