The vibrational energy of crystals is known to propagate in quantized sinusoidal waves called phonons. In the realm of nonlinear dynamics, however, nonlinear propagating waves are also possible in the form of cnoidal waves where wave displacements are concentrated in solitons separated by flatter regions – like a train of ocean waves rolling into shore. Nonlinear traveling waves have unique properties that are important in many disciplines including optical communications, conducting polymers, biology, magnetism, and nuclear physics. Yet, despite the crucial importance of crystal lattice vibrations in fundamental and applied science, nonlinear traveling waves have not been observed in ordinary crystals. Here we show that nonlinear traveling waves exist in fluorite-structured thoria, urania, and natural calcium fluoride using neutron scattering and first-principles calculations. These nonlinear waves are observed at temperatures ranging from 5 K up to 1200 K, extend to frequencies 30-40% higher than the maximum phonon frequency, and travel at velocities comparable to or higher than the fastest phonon. Given that these nonlinear modes are still observed at 5 K, our measurements imply that the quantum ground state consists of entangled phonons. Prior measurements at reactor-based sources did not probe the high energies where these modes are found because relatively few epithermal neutrons are produced at a reactor source. Our measurements were made possible by the abundant epithermal neutrons available at a spallation neutron source. The existence of these waves in three-dimensional crystals may have ramifications for a wide range of properties.