Borides are a family of materials with valuable properties for various applications. Their diverse structures and compositions, yet disparity in the constituent chemical elements for the known compounds, give elemental substitutions for prototypes great potential for material discovery. To explore uncharted material compositional space, we develop a workflow that joins high-throughput crystal structure prediction and automated diffraction pattern matching to discover new compounds with significant prediction and synthesis hurdles. Utilizing the workflow, we explore the empty Mg-Fe-B ternary compositional space, previously uncharted largely due to the immiscibility of Mg and Fe, as a paradigm. A total of 275 ternary boride prototypes are classified, using which we predict 23 (158) stable and metastable ternary phases within 50 (200) meV/atom above the convex hull. We identify Gd