We demonstrate a new particle acceleration mechanism using 800 nm laser radiation to accelerate relativistic electrons in a semi-infinite vacuum. The experimental demonstration is the first of its kind and is a proof of principle for the concept of laser-driven particle acceleration in a structure loaded vacuum. We observed up to 30 keV energy modulation over a distance of 1000 lambda, corresponding to a 40 MeV/m peak gradient. The energy modulation was observed to scale linearly with the laser electric field and showed the expected laser-polarization dependence. Furthermore, as expected, laser acceleration occurred only in the presence of a boundary that limited the laser-electron interaction to a finite distance.