The development of novel alloys that are specifically tailored for additive manufacturing (AM) is one of the current major challenges of the AM research community. However, the existing approaches can be further made efficient in exploring the vast material and process design space in AM. In the present work, we applied extreme high-speed laser material deposition (EHLA) to rapidly screen a wide range of chemical compositions and processing conditions within a single specimen. Combined high-throughput sample production and material characterization were used to explore the microstructure evolution and mechanical properties of additively manufactured advanced high strength steel. In-situ alloying of a base alloy (an austenitic steel) with pure Al in the range of 0-8 wt.% and flexible adjustment of the volumetric energy input enabled high-throughput sample production consisting of 20 individual chemistry-EHLA parameter combinations. These conditions were characterized using large-area EBSD analysis combined with EDS and spherical micro indentation stress-strain protocols. The significant influence of Al content and processing conditions on the behaviour of the investigated metastable base alloy allowed for efficient exploration of the respective mechanical properties. The derived process-structure-properties relationships are discussed based on the underlying physical mechanisms. The experimentally identified microstructure-property (SP) relationship was generalized using a machine learning (ML) approach. With this selected approach, the data-driven SP relationship can be described in terms of its uncertainty. In addition, the applicability of the methodology is critically evaluated.