We formulate a semiclassical theory for systems with spin-orbit interactions. Using spin coherent states, we start from the path integral in an extended phase space, formulate the classical dynamics of the coupled orbital and spin degrees of freedom, and calculate the ingredients of Gutzwiller's trace formula for the density of states. For a two-dimensional quantum dot with a spin-orbit interaction of Rashba type, we obtain satisfactory agreement with fully quantum-mechanical calculations. The mode-conversion problem, which arose in an earlier semiclassical approach, has hereby been overcome.