In certain methanogenic archaea a new amino acid, pyrrolysine (Pyl), is inserted at in-frame UAG codons in the mRNAs of some methyltransferases. Pyl is directly acylated onto a suppressor tRNA(Pyl) by pyrrolysyl-tRNA synthetase (PylRS). Due to the lack of a readily available Pyl source, we looked for structural analogues that could be aminoacylated by PylRS onto tRNA(Pyl). We report here the in vitro aminoacylation of tRNA(Pyl) by PylRS with two Pyl analogues: N-epsilon-d-prolyl-l-lysine (d-prolyl-lysine) and N-epsilon-cyclopentyloxycarbonyl-l-lysine (Cyc). Escherichia coli, transformed with the tRNA(Pyl) and PylRS genes, suppressed a lacZ amber mutant dependent on the presence of d-prolyl-lysine or Cyc in the medium, implying that the E. coli translation machinery is able to use Cyc-tRNA(Pyl) and d-prolyl-lysine-tRNA(Pyl) as substrates during protein synthesis. Furthermore, the formation of active beta-galactosidase shows that a specialized mRNA motif is not essential for stop-codon recoding, unlike for selenocysteine incorporation.