New observations of LS 5039, a High Mass X-ray Binary comprising a massive star and compact object, were carried out with the High Energy Stereoscopic System of Cherenkov Telescopes (H.E.S.S.) in 2005 at very high energy (VHE) gamma-ray energies. These observations reveal that its flux and energy spectrum are modulated with the 3.9 day orbital period of the binary system. This is the first time in gamma-ray astronomy that orbital modulation has been observed, and periodicity clearly established using ground-based gamma-ray detectors. The VHE gamma-ray emission is largely confined to half of the orbit, peaking around the inferior conjunction epoch of the compact object. For this epoch, there is also a hardening of the energy spectrum in the energy range between 0.2 TeV and a few TeV. The flux vs. orbital phase profile provides the first clear indication of gamma-ray absorption via pair production within an astrophysical source, a process which is expected to occur if the gamma-ray production site is situated within ~1 AU of the compact object. Moreover the production region size must be not significantly greater than the binary separation (~0.15 AU). Notably, these constraints are also considerably smaller than the collimated outflows or jets (extending out to ~1000 AU) observed in LS 5039. The spectral hardening could arise from variations with phase in the maximum electron energies, and/or the dominant VHE gamma-ray production mechanism.