We hypothesize that ‘given a set of elements in the Periodic Table, one can not only identify the stable compounds that can be formed but we can also identify those with the desired characteristics or properties’. To prove the hypothesis, we present a high-throughput strategy and design compositionally complex ceramics (C3) for extreme environments by establishing design rules that permit accelerated discovery. We focus on the design space consisting of three elements, Si-C-N, and identify all possible 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 this 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 hardness and stability.