Using first-principles density functional theory (DFT), we calculate the diffusivities of 32 different solute elements—all transition metals, together with Al and Si—in fcc cobalt within the formalism of the five-frequency model. For self-diffusion in fcc cobalt, we compare the accuracy of various approximations to the exchange-correlation energy functional of DFT in estimating the activation energy, and find that only the Perdew-Burke-Ernzerhof (PBE) approximation agrees well with experimental reports and all other functionals largely overestimate it. Our calculations also show that an accurate estimation of the self-diffusion coefficient requires explicit calculation of the effective jump frequency and vacancy formation entropy via phonons. Using accurate self-diffusion data and scaling all solute-related attempt frequencies with respect to the attempt frequency for self-diffusion using a simple relation involving the atomic mass and melting temperature of the solute yields solute diffusivities in excellent agreement with experiments, where such data is available. We find that large solutes spontaneously relax toward the nearest neighbor vacancy to relieve the misfit strain, and the extent of this relaxation correlates negatively with the migration energy. Thus, in general, larger solutes have lower migration energies and diffuse faster than smaller solutes in fcc cobalt. However, extremely large solutes, e.g., group III elements Sc, Y, Lu, tend to be trapped in an energy valley located halfway toward the vacancy, and monovacancy mediated diffusion may no longer be valid in such cases. Finally, for all the solutes considered, we systematically tabulate the diffusion-related quantities calculated—diffusion prefactors, migration and activation energies—constructing an extensive and accurate first-principles database for solute diffusion in fcc cobalt.