Creation of site-specifically labeled protein bioconjugates is an important tool for the molecular biologist and cell biologist. Chemical labeling methods, while versatile with respect to the types of moieties that can be attached, suffer from lack of specificity, often targeting multiple positions within a protein. Here we describe protocols for the chemoenzymatic labeling of proteins at the C-terminus using the bacterial transpeptidase, sortase A. We detail a protocol for the purification of an improved pentamutant variant of the Staphylococcus aureus enzyme (SrtA 5(o)) that exhibits vastly improved kinetics relative to the wild-type enzyme. Importantly, a protocol for the construction of peptide probes compatible with sortase labeling using techniques that can be adapted to any cellular/molecular biology lab with no existing infrastructure for synthetic chemistry is described. Finally, we provide an example of how to optimize the labeling reaction using the improved SrtA 5(o) variant.