The secular dynamics of a nonrelativistic charged particle in an electromagnetic wave can be described by the ponderomotive potential. Although ponderomotive electron-laser interactions at relativistic velocities are important for emerging technologies from laser-based particle accelerators to laser-enhanced electron microscopy, the effects of special relativity on the interaction have only been studied theoretically. Here, we use a transmission electron microscope to measure the position-dependent phase shift imparted to a relativistic electron wave function when it traverses a standing laser wave. The kinetic energy of the electrons is varied between 80 and 300 keV, and the laser standing wave has a continuous-wave intensity of 175 GW/cm^{2}. In contrast to the nonrelativistic case, we demonstrate that the phase shift depends on both the electron velocity and the wave polarization, confirming the predictions of a quasiclassical theory of the interaction. Remarkably, if the electron's speed is greater than 1/sqrt[2] of the speed of light, the phase shift at the electric field nodes of the wave can exceed that at the antinodes. In this case there exists a polarization such that the phase shifts at the nodes and antinodes are equal, and the electron does not experience Kapitza-Dirac diffraction. Our results thus provide new capabilities for coherent electron beam manipulation.