We present a density functional theory study of the first step of CH4 adsorption on the Ni(111) surface, dissociation into adsorbed CH3 and H. The rupture of the C-H bond occurs preferentially on top of a Ni atom, with a dissociation barrier of about 100 kJ/mol (including zero point corrections). The transition state involves considerable internal excitation of the molecule. The active C-H bond is both stretched to 1.6 Angstrom and tilted relative to the methyl group. A normal mode analysis shows that the reaction coordinate is mainly a C-H stretch, while the orientation of the C-H bond relative to the surface is responsible for the highest real mode. Alloying the surface with gold also affects the reactivity of the Ni atoms on adjacent surface sites. The dissociation barrier is increased by 16 and 38 kJ/mol for a Ni atom with one or two gold neighbors, respectively. We attribute these changes to a shift in the local density of d states at the nickel atoms in the neighborhood of gold.