Recombinant protein production is a widely used process, yet half of these experiments fail to be expressed in a variety of host cells. Here we show that translation initiation, the rate limiting step, is key to successful recombinant protein production. In particular, we show that the accessibility of translation initiation sites modelled using the mRNA base-unpairing across the Boltzmann’s ensemble is significantly more important than alternative features. This approach accurately predicts the successes or failures of expression experiments, which utilised Escherichia coli cells to express 11,430 recombinant proteins from over 189 diverse species. On this basis, we develop TIsigner that uses simulated annealing to modify up to the first nine codons of mRNAs with synonymous substitutions. We show that accessibility captures the key propensity beyond initiation sites, as a modest number of synonymous changes is sufficient to tune the recombinant protein expression levels. We build a stochastic simulation model and show that higher accessibility leads to higher protein production and slower cell growth, supporting the idea of protein cost, where cell growth is constrained by protein circuits during overexpression. Our tool for tuning protein expression is available as a web service at https://tisigner.com/. We also provide relevant web services, including prediction/optimisation of protein solubility, protein-protein interactions, and signal peptides.