We report the discovery of X-ray broad absorption lines (BALs) from the BAL quasar APM 08279+5255 originating from material moving at relativistic velocities with respect to the central source. The large flux magnification by a factor of similar to100 provided by the gravitational lens effect combined with the large redshift ( z = 3.91) of the quasar have facilitated the acquisition of the first high signal-to-noise X-ray spectrum of a quasar containing X-ray BALs. Our analysis of the X-ray spectrum of APM 08279+5255 places the rest-frame energies of the two observed absorption lines at 8.1 and 9.8 keV. The detection of each of these lines is significant at a greater than 99.9% confidence level based on the F-test. Assuming that the absorption lines are from Fe XXV Kalpha, the implied bulk velocities of the X-ray BALs are similar to0.2c and similar to0.4c, respectively. The observed high bulk velocities of the X-ray BALs combined with the relatively short recombination timescales of the X-ray absorbing gas imply that the absorbers responsible for the X-ray BALs are located at radii of less than or similar to2 x 10(17) cm, within the expected location of the UV absorber. With this implied geometry, the X-ray gas could provide the necessary shielding to prevent the UV absorber from being completely ionized by the central X-ray source, consistent with hydrodynamical simulations of line-driven disk winds. Estimated mass-outflow rates for the gas creating the X-ray BALs are typically less than a solar mass per year. Our spectral analysis also indicates that the continuum X-ray emission of APM 08279+5255 is consistent with that of a typical radio-quiet quasar with a spectral slope of Gamma 1.72(-0.05)(+0.06).