New highly oxygen-active materials may enhance many energy-related technologies by enabling efficient oxygen-ion transport at lower temperatures, e.g., below ≈400 ˚C. Interstitial oxygen conductors have the potential to realize such performance but have received far less attention than vacancy-mediated conductors. Here, we combine physically-motivated structure and property descriptors, ab initio simulations, and experiments to demonstrate an approach to discover new fast interstitial oxygen conductors. Multiple new families were found which adopt completely different structures from known oxygen conductors. From these families, we synthesized and studied oxygen kinetics in La4Mn5Si4O22+𝜹(LMS), a representative member of perrierite/chevkinite family. We found LMS has higher oxygen ionic conductivity than the widely used yttria-stabilized ZrO2, and among the highest surface oxygen exchange rates at intermediate temperature of known materials. The fast oxygen kinetics is the result of simultaneously active interstitial and interstitialcy diffusion pathways. This work developed and demonstrated a powerful approach for discovering new families of interstitial oxygen conductors and suggests many more such materials remain to be discovered.