A quantitative understanding of how conformational transitions contribute to enzyme catalysis and specificity remains a fundamental challenge. A suite of biophysical approaches was used to reveal several transient states of the enzyme:substrate complexes of the model DNA cytosine methyltransferase M.HhaI. Multidimensional, transverse relaxation-optimized NMR experiments show that M.HhaI has the same conformation with non-cognate and cognate DNA sequences. The high-affinity cognate-like mode requires the formation of a subset of protein-DNA interactions which drive the flipping of the target base from the helix and into the active site. Non-cognate substrates lacking these interactions undergo slow base flipping, and fluorescence tracking of the catalytic loop corroborates the NMR evidence for a loose, non-specific binding mode prior to base flipping and subsequent closure of the catalytic loop. This slow flipping transition defines the rate limiting step for the methylation of non-cognate sequences. Additionally, we present spectroscopic evidence for an intermediate along the base flipping pathway that has been predicted but never previously observed. These findings provide important details into how conformational rearrangements are used to balance specificity with catalytic efficiency.