ZrO₂(Y₂O₃)-graphite composites with a three-dimensional (3D) continuous structure were prepared by using a core-shell design of graphite and ZrO₂(Y₂O₃). 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 ZrO₂(Y₂O₃)-graphite composites with homogeneous composition. For the composites with 3D structure, the continuous ZrO₂ 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.