Single-atom catalysts (SACs) have attracted considerable attention in the catalysis community. However, fabricating intrinsically stable SACs on traditional supports (N-doped carbon, metal oxides, etc.) remains a formidable challenge, especially under high-temperature conditions. Here, we report a novel entropy-driven strategy to stabilize Pd single-atom on the high-entropy fluorite oxides (CeZrHfTiLa)Ox (HEFO) as the support by a combination of mechanical milling with calcination at 900 °C. Characterization results reveal that single Pd atoms are incorporated into HEFO (Pd1@HEFO) sublattice by forming stable Pd-O-M bonds (M = Ce/Zr/La). Compared to the traditional support stabilized catalysts such as Pd@CeO2, Pd1@HEFO affords the improved reducibility of lattice oxygen and the existence of stable Pd-O-M species, thus exhibiting not only higher low-temperature CO oxidation activity but also outstanding resistance to thermal and hydrothermal degradation. This work therefore exemplifies the superiority of high-entropy materials for the preparation of SACs.