Electrons in atoms possess both spin and orbital degrees of freedom. In non-relativistic quantum mechanics, these are independent, resulting in large degeneracies in atomic spectra. However, relativistic effects couple the spin and orbital motion leading to the well-known fine structure in their spectra. The electronic states in defect-free carbon nanotubes (NTs) are widely believed to be four-fold degenerate, due to independent spin and orbital symmetries, and to also possess electron-hole symmetry. Here we report measurements demonstrating that in clean NTs the spin and orbital motion of electrons are coupled, thereby breaking all of these symmetries. This spin-orbit coupling is directly observed as a splitting of the four-fold degeneracy of a single electron in ultra-clean quantum dots. The coupling favours parallel alignment of the orbital and spin magnetic moments for electrons and anti-parallel alignment for holes. Our measurements are consistent with recent theories that predict the existence of spin-orbit coupling in curved graphene and describe it as a spin-dependent topological phase in NTs. Our findings have important implications for spin-based applications in carbon-based systems, entailing new design principles for the realization of qubits in NTs and providing a mechanism for all-electrical control of spins in NTs.