Protein-RNA recognition between aminoacyl-tRNA synthetases and tRNA is highly specific and essential for cell viability. We investigated the structure-function relationships involved in the interaction of the Escherichia coli tRNA(Asp) acceptor stem with aspartyl-tRNA synthetase. The goal was to isolate functionally active mutants and interpret them in terms of the crystal structure of the synthetase-tRNA(Asp) complex. Mutants were derived from Saccharomyces cerevisiae tRNA(Asp), which is inactive with E. coli aspartyl-tRNA synthetase, allowing a genetic selection of active tRNAs in a tRNA(Asp) knockout strain of E. coli. The mutants were obtained by directed mutagenesis or library selections that targeted the acceptor stem of the yeast tRNA(Asp) gene. The mutants provide a rich source of tRNA(Asp) sequences, which show that the sequence of the acceptor stem can be extensively altered while allowing the tRNA to retain substantial aminoacylation and cell-growth functions. The predominance of tRNA backbone-mediated interactions observed between the synthetase and the acceptor stem of the tRNA in the crystal and the mutability of the acceptor stem suggest that many of the corresponding wild-type bases are replaceable by alternative sequences, so long as they preserve the initial backbone structure of the tRNA. Backbone interactions emerge as an important functional component of the tRNA-synthetase interaction.