We have measured the temporal shortening of an ultraintense laser pulse interacting with an underdense plasma. When interacting with strongly nonlinear plasma waves, the laser pulse is shortened from 38 +/- 2 fs to the 10-14 fs level, with a 20% energy efficiency. The laser ponderomotive force excites a wakefield, which, along with relativistic self-phase modulation, broadens the laser spectrum and subsequently compresses the pulse. This mechanism is confirmed by 3D particle in cell simulations.