We present multi-slit radial velocity measurements for 111 stars in the direction of the Virgo Stellar Stream (VSS). The stars were photometrically selected to be probable main-sequence stars in the Galactic halo. When compared with the radial velocity distribution expected for the halo of the Milky Way, as well as the distribution seen in a control field, we observe a significant excess of negative velocity stars in the field, which can likely be attributed to the presence of a stellar stream. This kinematic excess peaks at a Galactic standard of rest radial velocity of -75 km s-1. A rough distance estimate suggests that this feature extends from ~15 kpc out to, and possibly beyond, the ~30 kpc limit of the study. The mean velocity of these stars is incompatible with those of the VSS itself (Vgsr ~ 130 km s-1), which we weakly detect, but it is consistent with radial velocity measurements of nearby 2MASS M-giants and SDSS+SEGUE K/M-giants and blue horizontal branch stars that constitute the leading tidal tail of the Sagittarius dwarf spheroidal galaxy. Some oblate models for the shape of the Milky Way's dark matter halo predict that the leading arm of the Sagittarius Stream should pass through this volume, and have highly negative (Vgsr <~ -200 km s-1) radial velocities, as it descends down from the northern Galactic hemisphere toward the Galactic plane. The kinematic feature observed in this study, if it is in fact Sagittarius debris, is not consistent with these predictions, and instead, like other leading stream radial velocity measurements, is consistent with a recently published triaxial halo model, or, if axisymmetry is imposed, favors a prolate shape for the Galactic halo potential. However, a rough distance estimate to the observed kinematic feature places it somewhat closer (D ~ 15-30 kpc) than the Sagittarius models predict (D ~ 35-45 kpc). This paper includes data gathered with the 6.5 m Magellan Telescopes located at Las Campanas Observatory, Chile.