NMR studies of multi-domain protein complexes provide unique insight into their molecular interactions and dynamics in solution. For large proteins domain-selective isotope labeling is desired to reduce signal overlap, but available methods require extensive optimization and often give poor ligation yields. We present an optimized strategy for segmental labeling of multi-domain proteins using the S. aureus transpeptidase Sortase A. Critical improvements compared to existing protocols are (1) the efficient removal of cleaved peptide fragments by centrifugal filtration and (2) a strategic design of cleavable and non-cleavable affinity tags for purification. Our approach enables routine production of milligram amounts of purified segmentally labeled protein for NMR and other biophysical studies.