The protein ProQ has recently been identified as a global RNA chaperone in $Salmonella$, and a similar role is anticipated for its numerous homologues in divergent bacterial species. We report the solution structure of $Escherichia\; coli$ ProQ, revealing an N-terminal FinO-like domain, a C-terminal domain that unexpectedly has a Tudor-domain fold commonly found in eukaryotes, and an elongated bridging intra-domain linker that is flexible but nonetheless incompressible. Structure based sequence analysis suggests that the Tudor domain was acquired through horizontal gene transfer and gene fusion to the ancestral FinO-like domain. Through a combination of biochemical and biophysical approaches, we have mapped putative RNA binding surfaces on all three domains of ProQ and modelled the protein's conformation in the apo and RNA-bound forms. Taken together, these data suggest how the FinO, Tudor and linker domains of ProQ cooperate to recognise complex RNA structures and serve to promote RNA-mediated regulation.