We report ab initio calculations of C59Ni and C60Ni clusters using a fully self-consistent density-functional method that employs linear combinations of atomic orbitals as basis sets, standard nonlocal, norm-conserving pseudopotentials, and a generalized gradient approximation to exchange and correlation. Our results for C59Ni show that the replacement of a C atom of the C-60 fullerene cage by a Ni atom yields (on relaxation) a stable substitutionally doped fullerene, in keeping with both recent density-functional calculations using the local spin density approximation and the results of mass spectrometry. For C60Ni, our calculations show that the most favorable site for the Ni atom is a bridge site over a C-C double bond.