The dissociation of methane on a nickel catalyst is a key step in steam reforming of natural gas for hydrogen production. Despite substantial effort in both experiment and theory, there is still no atomic-scale description of this important gas-surface reaction. We report quantum state-resolved studies, using pulsed laser and molecular beam techniques, of vibrationally excited methane reacting on the nickel (100) surface. For doubly deuterated methane (CD2H2), we observed that the reaction probability with two quanta of excitation in one C-H bond was greater (by as much as a factor of 5) than with one quantum in each of two C-H bonds. These results clearly exclude the possibility of statistical models correctly describing the mechanism of this process and attest to the importance of full-dimensional calculations of the reaction dynamics.