Staphylococcus aureus sortase A is a transpeptidase that has been extensively exploited for site-specific modification of proteins and was originally used to attach a labeling reagent containing an LPXTG recognition sequence to a protein or peptide with an N-terminal glycine. Sortase mutants with other recognition sequences have also been reported, but in all cases, the reversibility of the transpeptidation reaction limits the efficiency of sortase-mediated labeling reactions. For the wildtype sortase, depsipeptide substrates, in which the scissile peptide bond is replaced with an ester, allow effectively irreversible sortase-mediated labeling as the alcohol byproduct is a poor competing nucleophile. In this paper, the use of depsipeptide substrates for evolved sortase variants is reported. Substrate specificities of three sortases have been investigated allowing identification of an orthogonal pair of enzymes accepting LPEToG and LPESoG depsipeptides, which have been applied to dual N-terminal labeling of a model protein mutant containing a second, latent N-terminal glycine residue. The method provides an efficient orthogonal site-specific labeling technique that further expands the biochemical protein labeling toolkit.