Elasto-inertial turbulence (EIT) is a new, two-dimensional chaotic flow state observed in polymer solutions with possible connections to inertialess elastic turbulence and drag-reduced Newtonian turbulence. In this Letter, we argue that the origins of EIT are fundamentally different from Newtonian turbulence by finding a dynamical connection between EIT and an elasto-inertial linear instability recently found at high Weissenberg numbers [Garg et al., Phys. Rev. Lett. 121, 024502 (2018)]. This link is established by isolating the first known exact coherent structures in viscoelastic parallel flows—nonlinear elasto-inertial traveling waves (TWs)—borne at the linear instability and tracking them down to substantially lower Weissenberg numbers where EIT exists. These TWs have a distinctive “arrowhead" structure in the polymer stretch field and can be clearly recognized albeit transiently in EIT as well as being attractors for EIT dynamics if the Weissenberg number is sufficiently large. Our findings suggest that the dynamical systems picture in which Newtonian turbulence is built around the coexistence of many (unstable) simple invariant solutions populating phase space carries over to EIT, though these solutions rely on elasticity to exist.