The observation of traveling breathers (TBs) with large-amplitude oscillatory tails realizes an almost 50-year-old theoretical prediction [E. A. Kuznetsov and A. V. Mikhailov, Stability of stationary waves in nonlinear weakly dispersive media, Zh. Eksp. Teor. Fiz. 67, 1717 (1974) ZETFA70044-4510[E. A. Kuznetsov and A. V. MikhailovSov. Phys. JETP 40, 855 (1975)] SPHJAR0038-5646] and generalizes the notion of a breather. Two strongly nonlinear TB families are created in a core-annular flow by interacting a soliton and a nonlinear periodic (cnoidal) carrier. Bright and dark TBs are observed to move faster or slower, respectively, than the carrier while imparting a phase shift. Agreement with model equations is achieved. Scattering of the TBs is observed to be physically elastic. The observed TBs generalize to many continuum and discrete systems.