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. To elucidate its dynamics, we have performed quantum state resolved studies of vibrationally excited methane reacting on the Ni(100) surface using pulsed laser and molecular beam techniques. We observed up to a factor of 5 greater reaction probability for methane-d2 with two quanta of excitation in one C-H bond versus a nearly isoenergetic state with one quanta in each of two C-H bonds. For CH4, stimulated Raman pumping is used to probe the reactivity of the totally symmetric C-H stretch vibration for comparison with reactivity of CH4 excited to the infrared active antisymmetric C-H stretch vibration. The observed reactivities point to a transition state structure which has one of the C-H bonds significantly elongated. Our results also clearly exclude the possibility of statistical models correctly describing the mechanism of this process and emphasize the importance of full-dimensional calculations of the reaction dynamics.