We examine the possibility of traveling-wave solutions within the nonlinear Euler-Heisenberg electrodynamics. Since this theory resembles in its form the electrodynamics in matter, it is a priori not clear if there exist traveling-wave solutions with a new dispersion relation for $\ensuremath{\omega}(k)$ or if the Euler-Heisenberg theory stringently imposes $\ensuremath{\omega}=k$ for any arbitrary ansatz $\mathbf{E}(\ensuremath{\xi})$ and $\mathbf{B}(\ensuremath{\xi})$ with $\ensuremath{\xi}\ensuremath{\equiv}\mathbf{k}\ifmmode\cdot\else\textperiodcentered\fi{}\mathbf{r}\ensuremath{-}\ensuremath{\omega}t$. We show that the latter scheme applies for the Euler-Heisenberg theory, but point out the possibility of new solutions with $\ensuremath{\omega}\ensuremath{\ne}k$ if we go beyond the Euler-Heisenberg theory, allowing strong fields. In case of the Euler-Heisenberg theory the quantum-mechanical effect of the traveling-wave solutions remains in $\ensuremath{\hbar}$ corrections to the energy density and the Poynting vector.