In many γ-proteobacteria, the RpoS/σS sigma factor associates with the core RNAP (RNA polymerase) to modify global gene transcription in stationary phase and under stress conditions. The small regulatory protein Crl stimulates the association of σS with the core RNAP in Escherichia coli and Salmonella enterica serovar Typhimurium, through direct and specific interaction with σS. The structural determinants of Crl involved in σS binding are unknown. In the present paper we report the X-ray crystal structure of the Proteus mirabilis Crl protein (CrlPM) and a structural model for Salmonella Typhimurium Crl (CrlSTM). Using a combination of in vivo and in vitro assays, we demonstrated that CrlSTM and CrlPM are structurally similar and perform the same biological function. In the Crl structure, a cavity enclosed by flexible arms contains two patches of conserved and exposed residues required for σS binding. Among these, charged residues that are likely to be involved in electrostatic interactions driving Crl-σS complex formation were identified. CrlSTM and CrlPM interact with domain 2 of σS with the same binding properties as with full-length σS. These results suggest that Crl family members share a common mechanism of σS binding in which the flexible arms of Crl might play a dynamic role.