We present a high-throughput strategy to design compositionally complex ceramics (C3) for extreme environments by establishing design rules that permit accelerated discovery. The first phase – i.e., the ‘exploitation’ phase – focuses on well-understood, design spaces (e.g., Si-C-N, Al-O-N systems), by identifying new stoichiometries and structures. Evolutionary structure searches coupled to density-functional theory (DFT) calculations are applied to predict the ground state and metastable structures within a given system. These searches aim to not only find structures with low energies (i.e., on or close to the convex hull), but also maximize the targeted property (in this case, hardness). Hence, the algorithm serves to both, generate and screen data within the given system to produce structures with the desired stability and properties. The data obtained throughout these structure searches is exploited in a machine-learning model that is trained on the fly and can accelerate the structure prediction and provide an accurate and efficient surrogate model of the energy (and hardness) landscape. Through this framework, we aim to develop chemical design rules to answer the fundamental question of how chemical additions to the structure affect its hardness and stability.