Methyl-specific isotope labeling is a powerful tool to study the structure, dynamics and interactions of large proteins and protein complexes by solution-state NMR. However, widespread applications of this methodology have been limited by challenges in obtaining confident resonance assignments. Here, we present Methyl Assignments Using Satisfiability (MAUS), leveraging Nuclear Overhauser Effect cross-peak data, peak residue type classification and a known 3D structure or structural model to provide robust resonance assignments consistent with all the experimental inputs. Using data recorded for targets with known assignments in the 10-45 kDa size range, MAUS outperforms existing methods by up to 25,000 times in speed while maintaining 100% accuracy. We derive de novo assignments for multiple Cas9 nuclease domains, demonstrating that the methyl resonances of multi-domain proteins can be assigned accurately in a matter of days, while reducing biases introduced by manual pre-processing of the raw NOE data. MAUS is available through an online web-server.