Quasiparticle interference patterns measured by scanning tunneling microscopy can be used to study the local electronic structure of metal surfaces and high-temperature superconductors. Here, we show that even in nonmagnetic systems the spin of the quasiparticles can have a profound effect on the interference patterns. On Bi(110), where the surface state bands are not spin degenerate, the patterns are not related to the dispersion of the electronic states in a simple way. In fact, the features which are expected for the spin-independent situation are absent and the observed interference patterns can be interpreted only by taking spin-conserving scattering events into account.