We report an analysis of the nuclear dependence of the yield of Drell-Yan dimuons from the 800 GeV/c proton bombardment of 2H, C, Ca, Fe, and W targets. Employing a new formulation of the Drell-Yan process in the rest frame of the nucleus, this analysis examines the effect of initial-state energy loss and shadowing on the nuclear-dependence ratios versus the incident proton's momentum fraction and dimuon effective mass. The resulting energy loss per unit path length is -dE/dz = 2.32+/-0.52+/-0.5 GeV/fm. This is the first observation of a nonzero energy loss of partons traveling in a nuclear environment.