We report the first systematic evolution and study of tRNA variants that are able to read a set of UAGN (N = A, G, U, C) codons in a genomically recoded E. coli strain that lacks any endogenous in-frame UAGN sequences and release factor 1. Through randomizing bases in anticodon stem-loop followed by a functional selection, we identified tRNA mutants with significantly improved UAGN decoding efficiency, which will augment the current efforts on genetic code expansion through quadruplet decoding. We found that an extended anticodon loop with an extra nucleotide was required for a detectable efficiency in UAGN decoding. We also observed that this crucial extra nucleotide was converged to a U (position 33.5) in all of the top tRNA hits no matter which UAGN codon they suppress. The insertion of U33.5 in the anticodon loop likely causes tRNA distortion and affects anticodon-codon interaction, which induces +1 frameshift in the P site of ribosome. A new model was proposed to explain the observed features of UAGN decoding. Overall, our findings elevate our understanding of the +1 frameshift mechanism and provide a useful guidance for further efforts on the genetic code expansion using a non-canonical quadruplet reading frame.