Chemical relaxation phenomena, including photochemistry and electron transfer processes, form a vigorous area of research in which nonadiabatic dynamics plays a fundamental role. However, for electronic systems with spin degrees of freedom, there are few if any applicable and practical quasiclassical methods. Here, we show that for nonadiabatic dynamics with two electronic states and a complex-valued Hamiltonian that does not obey time-reversal symmetry (as relevant to many coupled nuclear-electronic-spin systems), the optimal semiclassical approach is to generalize Tully's surface hopping dynamics from coordinate space to phase space. In order to generate the relevant phase-space adiabatic surfaces, one isolates a proper set of diabats, applies a phase gauge transformation, and then diagonalizes the total Hamiltonian (which is now parameterized by both R and P). The resulting algorithm is simple and valid in both the adiabatic and nonadiabatic limits, incorporating all Berry curvature effects. Most importantly, the resulting algorithm allows for the study of semiclassical nonadiabatic dynamics in the presence of spin-orbit coupling and/or external magnetic fields. One expects many simulations to follow as far as modeling cutting-edge experiments with entangled nuclear, electronic, and spin degrees of freedom, e.g., experiments displaying chiral-induced spin selectivity.