Methyl-transverse relaxation optimized spectroscopy is rapidly becoming the preferred NMR technique for probing structure and dynamics of very large proteins up to ~1 MDa in molecular size. Data interpretation, however, necessitates assignment of methyl groups which still presents a very challenging and time-consuming process. Here we demonstrate that, in combination with a known 3D structure, paramagnetic relaxation enhancement (PRE), induced by nitroxide spin-labels incorporated at only a few surface-exposed engineered cysteines, provides fast, straightforward and robust access to methyl group resonance assignments, including stereoassignments for the methyl groups of leucine and valine. Neither prior assignments, including backbone assignments, for the protein, nor experiments that transfer magnetization between methyl groups and the protein backbone, are required. PRE-derived assignments are refined by 4D methyl–methyl nuclear Overhauser enhancement data, eliminating ambiguities and errors that may arise due to the high sensitivity of PREs to the potential presence of sparsely-populated transient states.