High-strength alloys are intimately connected to human development, from the bronze age to the current applications in aerospace and energy. State-of-the-art alloys are engineered to harness strengthening mechanisms across scales, from crystal-level processes to complex hierarchical microstructures that are designed to hinder the mobility of dislocations and other carriers of plasticity. In this context, complex concentrated alloys (CCAs) are attractive since they can exhibit very high strength at the single-phase level, which can be further enhanced via incorporation of the second phase and microstructural optimization. Unfortunately, the optimization of CCAs is notoriously difficult due to the high dimensionality of the design space. Here, a combination of physics-based modeling, machine learning, experimental fabrication, and multi-resolution characterization results is demonstrated in the discovery of the hardest Al-containing BCC-based alloy, surpassing the current state of the art by 31%. Importantly, this is accomplished with only 24 experiments within a design space consisting of 67,536 possible candidates. The approach can be generalized to other alloys, and the resulting materials are of interest in applications ranging from aerospace to nuclear power.