ZrO2(Y2O3)-graphite composites with a three-dimensional (3D) continuous structure were prepared by using a core-shell design of graphite and ZrO2(Y2O3). The effect of structure on the friction-reducing and anti-wear mechanisms from room temperature to 700 °C was investigated. During high-temperature friction, abrasive wear and brittle fracture are the main wear mechanisms for ZrO2(Y2O3)-graphite composites with homogeneous composition. For the composites with 3D structure, the continuous ZrO2 matrix with high load-carrying capacity and the formation of a dense friction layer with self-lubricating and thermal oxidation resistance improve the tribological properties significantly, reducing the coefficient of friction by about 10% and the wear rate by nearly two orders of magnitude when coupled with GH4169 alloys at 600 °C.