Nonlinear surface optics is being developed as a useful new tool in surface science. In this work, we calculate the second-order magneto-optical response function in order to determine the nonlinear magneto-optical Kerr effect. This is applied to the surface of ferromagnetic nickel. We take into account the realistic spin-polarized nickel band structure and the spin-orbit coupling, but treat the transition-matrix elements as constants in a first approximation. We calculate nonlinear Kerr spectra which should be observable in surface second-harmonic-generation experiments. As a check of our calculations we determine the linear magneto-optical Kerr effect (MOKE) spectra for bulk nickel and find good agreement with experiment.