Thin films made from transition metal carbides (TMCs) exhibit outstanding thermal stability, with melting points nearly reaching 4000 °C, and show exceptional mechanical performance, including high hardness. These characteristics designate PVD-deposited TMCs as vital materials for demanding aerospace and tooling applications. However, their inherently limited oxidation resistance necessitates the incorporation of strong oxide-forming elements, such as Al and Si, to enhance their high-temperature behavior. The present study focuses on metastable, FCC-structured TM–X–C (TM = Ti, Zr, Hf, Ta, W; X = Al, Si) solid solutions. Density Functional Theory (DFT) is employed to assess metastable solubility trends through formation energies and lattice distortions. These theoretical insights are then linked to an extensive experimental study, in which more than 260 distinct compositions across the ten ternary systems are synthesized using combinatorial magnetron sputtering. Subsequent characterization of phase formation, mechanical properties, and oxidation resistance is performed using X-ray diffraction, nanoindentation (CSM method), and Transmission Electron Microscopy (TEM) for selected samples. This integrated investigation of structure-property relationships in ternary TMC thin films offers valuable understanding of a largely unexplored compositional space and highlights new prospects for advanced high-performance applications.