Expression patterns in Escherichia coli of two small archaeal proteins with a natural content of about 30% rare codons were analyzed. The proteins, a histone-like protein from Sulfolobus shibatae (Ssh10), and a glutaredoxin-like protein from Methanobacterium thermoautotrophicum (mtGrx), were produced with expression plasmids encoding wild-type genes, codon-optimized synthetic, and GST-fusion genes. These constructs were expressed in BL21 (DE3), its LysS derivative, and modified strains carrying copies for rare codon tRNAs or deletions in the RNAseE gene. Both Ssh10 and mtGrx expression levels were constitutively high in BL21(DE3) and its derivatives, with the exception of the LysS phenotype, which prevented high level expression of the Ssh10 wild-type gene. Surprisingly, a codon-optimized mtGrx gene construct displayed undetectable levels of protein production. The translational block observed with the synthetic mtGrx gene could be circumvented by using a synthetic mtGrx-glutathione S-transferase (GST) fusion construct or by in vitro translation. Taken together, the results underscore the importance of mRNA levels and RNA stability, but not necessarily tRNA abundance for efficient heterologous protein production in E. coli.