Do coding and regulatory segments of a gene co-evolve with each-other? Seeking answers to this question, here we analyze the case of Escherichia coli ribosomal protein S15, that represses its own translation by specifically binding its messenger RNA (rpsO mRNA) and stabilizing a pseudoknot structure at the upstream untranslated region, thus trapping the ribosome into an incomplete translation initiation complex. In the absence of S15, ribosomal protein S1 recognizes rpsO and promotes translation by melting this very pseudoknot. We employ a robust statistical method to detect signatures of positive epistasis between residue site pairs and find that biophysical constraints of translational regulation (S15-rpsO and S1-rpsO recognition, S15-mediated rpsO structural rearrangement, and S1-mediated melting) are strong predictors of positive epistasis. Transforming the epistatic pairs into a network, we find that signatures of two different, but interconnected regulatory cascades are imprinted in the sequence-space and can be captured in terms of two dense network modules that are sparsely connected to each other. This network topology further reflects a general principle of how functionally coupled components of biological networks are interconnected. These results depict a model case, where translational regulation drives characteristic residue-level epistasis—not only between a protein and its own mRNA but also between a protein and the mRNA of an entirely different protein. © 2018 Wiley Periodicals, Inc.