To achieve a kind of graphite-based bonded solid lubricating coating with excellent lubricity at high temperature, a graphite coating was fabricated on Inconel 718 substrate using a binder of aluminum chromium phosphate (ACP). The sliding friction and wear behavior of the coatings was evaluated by a reciprocating alumina ball-on-flat specimen geometry from room temperature (RT) to 700 °C. The structures and morphologies of the graphite phosphate coating were analyzed by X-ray diffraction, Fourier transform infrared spectrometry, X-ray photoelectron spectroscopy, Raman spectroscopy and scanning electron microscopy. The graphite phosphate coating exhibited stable and low friction coefficients from RT to 700 °C, except for the range of 200–300 °C. Results are explained on the basis of a reaction between phosphorus in the ACP binder and the dangling covalent bonds of the graphite to prevent its oxidation. Simultaneously, the elimination of adsorbed water vapor and the presence of a large degree of crystal defects in the graphite are responsible for the failure of the graphite phosphate coating at 200–300 °C. As a result, the wear mechanism of graphite phosphate coating at elevated temperatures is particularly analyzed and discussed in this work.