We find that the optical properties of carbon nanotubes reflect remarkably strong effects of exciton-phonon coupling. Tight-binding calculations show that a significant fraction of the spectral weight of the absorption peak is transferred to a distinct exciton+phonon sideband, which is peaked at around 200 meV above the main absorption peak. This sideband provides a distinctive signature of the excitonic character of the optical transition. The exciton-phonon coupling is reflected in a dynamical structural distortion, which contributes a binding energy of up to 100 meV. The distortion is surprisingly long ranged, and is strongly dependent on chirality.