We reveal that spatially localized vortex solitons become stable in self-focusing nonlinear media when the vortex symmetry-breaking azimuthal instability is eliminated by a nonlocal nonlinear response. We study the main properties of different types of vortex beams and discuss the physical mechanism of the vortex stabilization in spatially nonlocal nonlinear media.