We show that QED nonlinear effects imply a phase correction to the linear evolution of electromagnetic waves in vacuum. We provide explicit solutions of the modified Maxwell equations for the propagation of a superposition of two plane waves and calculate analytically and numerically the corresponding phase shift. This provides a new framework for the search of all-optical signatures of photon-photon scattering in vacuum. In particular, we propose an experiment for measuring the phase shift in projected high-power laser facilities.