Pyrrolysyl-tRNA synthetase (PylRS) is a major tool in genetic code expansion using noncanonical amino acids, yet its structure and function are not completely understood. Here we describe the crystal structure of the previously uncharacterized essential N-terminal domain of this unique enzyme in complex with tRNAPyl. This structure explains why PylRS remains orthogonal in a broad range of organisms, from bacteria to humans. The structure also illustrates why tRNAPyl recognition by PylRS is anticodon independent: the anticodon does not contact the enzyme. Then, using standard microbiological culture equipment, we established a new method for laboratory evolution-a noncontinuous counterpart of the previously developed phage-assisted continuous evolution. With this method, we evolved novel PylRS variants with enhanced activity and amino acid specificity. Finally, we employed an evolved PylRS variant to determine its N-terminal domain structure and show how its mutations improve PylRS activity in the genetic encoding of a noncanonical amino acid.