Regulation of protein synthesis is an essential step of gene expression. This process is under the control of cis-acting RNA elements and trans-acting factors. Gemin5 is a multifunctional RNA-binding protein organized in distinct domains. The protein bears a non-canonical RNA-binding site, designated RBS1, at the C-terminal end. Among other cellular RNAs, the RBS1 region recognizes a sequence located within the coding region of Gemin5 mRNA, termed H12. Expression of RBS1 stimulates translation of RNA reporters carrying the H12 sequence, counteracting the negative effect of Gemin5 on global protein synthesis. A computational analysis of RBS1 protein and H12 RNA variability across the evolutionary scale predicts coevolving pairs of amino acids and nucleotides. RBS1 footprint and gel-shift assays indicated a positive correlation between the identified coevolving pairs and RNA-protein interaction. The coevolving residues of RBS1 contribute to the recognition of stem-loop SL1, an RNA structural element of H12 that contains the coevolving nucleotides. Indeed, RBS1 proteins carrying substitutions on the coevolving residues P1297 or S1299S1300, drastically reduced SL1-binding. Unlike the wild type RBS1 protein, expression of these mutant proteins in cells failed to enhance translation stimulation of mRNA reporters carrying the H12 sequence. Therefore, the PXSS motif within the RBS1 domain of Gemin5 and the RNA structural motif SL1 of its mRNA appears to play a key role in fine-tuning the expression level of this essential protein. © 2020 Informa UK Limited, trading as Taylor & Francis Group.