Protein ubiquitination is a post-translational modification that regulates almost all aspects of eukaryotic biology. Here we discover the first routes for the efficient site-specific incorporation of delta-thiol-L-lysine (7) and delta-hydroxy-L-lysine (8) into recombinant proteins, via evolution of a pyrrolysyl-tRNA synthetase/tRNA(CUA) pair. We combine the genetically directed incorporation of 7 with native chemical ligation and desulfurization to yield an entirely native isopeptide bond between substrate proteins and ubiquitin. We exemplify this approach by demonstrating the synthesis of a ubiquitin dimer and the first synthesis of ubiquitinated SUMO.