Short peptide tags S6 and A1, each 12 residues in length, were identified from a phage-displayed peptide library as efficient substrates for site-specific protein labeling catalyzed by Sfp and AcpS phosphopantetheinyl transferases (PPTases), respectively. S6 and A1 tags were selected for useful levels of orthogonality in reactivities with the PPTases: the catalytic efficiency, kcat/Km of Sfp-catalyzed S6 serine phosphopantetheinylation was 442-fold greater than that for AcpS. Conversely, the kcat/Km of AcpS-catalyzed A1 labeling was 30-fold higher than that for Sfp-catalyzed A1 labeling. S6 and A1 peptide tags can be fused to N- or C-termini of proteins for orthogonal labeling of target proteins in cell lysates or on live cell surfaces. The development of the orthogonal S6 and A1 tags represents a significant enhancement of PPTase-catalyzed protein labeling, allowing tandem or iterative covalent attachment of small molecules of diverse structures to the target proteins with high efficiency and specificity.