We demonstrate that electron-phonon interaction in quantum dots embedded in one-dimensional systems leads to pronounced, non-Markovian decoherence of optical transitions. The experiments that we present focus on the line shape of photoluminescence from low-temperature axially localized carbon nanotube excitons. The independent boson model that we use to model the phonon interactions reproduces with very high accuracy the broad and asymmetric emission lines and the weak red-detuned radial breathing mode replicas observed in the experiments. The intrinsic phonon-induced pure dephasing of the zero-phonon line is 2 orders of magnitude larger than the lifetime broadening and is a hallmark of the reduced dimensionality of the phonon bath. The non-Markovian nature of this decoherence mechanism may have adverse consequences for applications of one-dimensional systems in quantum information processing.