Despite more than 50 years of effort, the origin of the genetic code remains enigmatic. Among different theories, the stereochemical hypothesis suggests that the code evolved as a consequence of direct interactions between amino acids and appropriate bases. If indeed true, such physicochemical foundation of the mRNA/protein relationship could also potentially lead to novel principles of protein-mRNA interactions in general. Inspired by this promise, we have recently explored the connection between the physicochemical properties of mRNAs and their cognate proteins at the proteome level. Using experimentally and computationally derived measures of solubility of amino acids in aqueous solutions of pyrimidine analogs together with knowledge-based interaction preferences of amino acids for different nucleobases, we have revealed a statistically significant matching between the composition of mRNA coding sequences and the base-binding preferences of their cognate protein sequences. Our findings provide strong support for the stereochemical hypothesis of genetic code’s origin and suggest the possibility of direct complementary interactions between mRNAs and cognate proteins even in present-day cells.