We present a combined experimental and theoretical study of cold collisions between bismuth and helium atoms in strong magnetic fields and demonstrate that the spin-orbit interaction coupling between different nonrelativistic states of Bi leads to rapid Zeeman relaxation. The Zeeman relaxation of Bi in the ground electronic state is found to be very efficient due to the admixture of electronic excited states which show an interaction anisotropy due to their nonzero electronic orbital angular momentum. Our results indicate that dense ensembles of heavy relativistic atoms will generally be unstable in magnetic traps due to significant spin relaxation induced by spin-orbit interactions.