The Escherichia coli regulatory protein StpA bears striking similarity to the chromatin-associated protein H-NS. These two proteins have many structural, functional and mechanistic parallels. Although H-NS is more abundant in the cell, both proteins act as transcriptional regulators, both bind to curved DNA and both restrain DNA supercoils. However, StpA is better able to promote RNA annealing and trans-splicing in vitro. In this study, phylogenetic analyses and experiments to examine the protease sensitivity of StpA and H-NS suggest a similar structure for the two proteins. Both proteins consist of two structured domains separated by an exposed protease-sensitive linker. The N-terminal (StpA-NterL) and C-terminal (StpA-CterL) domains of StpA, as well as the full-length StpA and H-NS proteins, were cloned, overproduced in E. coli and purified to homogeneity. StpA-CterL, but not StpA-NterL, promotes strand annealing of complementary RNA oligonucleotides and in vitro trans-splicing of a model group I intron. Both StpA and StpA-CterL exhibited stronger RNA-modulating activity than H-NS. Phylogenetic analyses showed that the N-terminal and C-terminal domains can exist autonomously. The phylogenetic and experimental data are compatible with a two-domain model for StpA and H-NS, with independently functioning modules joined by a non-conserved linker, and with the observed RNA-related activities residing entirely within the C-terminal domain.