We report a numerical study of crystal nucleation in a system of weakly charged colloids. The interaction between the colloids is approximated by a repulsive hard-core Yukawa potential. We studied the dependence of the nucleation barrier and the nucleation rate on supersaturation as a function of both contact value and range of the interaction potential. We find that, at the same volume fraction, nucleation is much faster for these soft colloids than for hard spheres. This is partly because fluid-solid coexistence in charged colloids occurs at lower volume fractions than for hard spheres. But, in addition, the softness of the potential has a pronounced direct effect on the nucleation barrier through a lowering of the solid-liquid surface free energy. Moreover, the softness of the potential directly affects the pathway for crystal nucleation: even when the stable crystal phase has a face-centred cubic structure, we find that the initial crystal nuclei have a bcc structure.