Boron-based materials are highly desirable for their promising mechanical properties, rendering them ideal for various industrial applications. In this study, we take advantage of the two unique metal Wyckoff sites in the prototype structures V3B2 (4h and 2a) and Cr5B3 (16h and 4c). These two sites were populated by two different metals, M ' and M '', forming novel B-based ternary M ' 2M '' B2 and M ' 4M '' B3 compounds. A high-throughput phase stability search encompassing a total of 2738 compositions with M ' and M '' being occupied systematically with Al, Si, Sc, Ti, V, Cr, Mn, Fe, Co, Ni, Cu, Zn, Ga, Ge, Y, Zr, Nb, Mo, Tc, Ru, Rh, Pd, Ag, Cd, In, Sn, Hf, Ta, W, Re, Os, Ir, Pt, Au, Hf, Tl, and Pb was performed. The thermodynamic phase stability of the simulated materials was assessed by evaluating the formation enthalpy, Delta Hcp for all compostions with chemical order and disorder for selective compositions. In total, 56 ternary phases were identified as stable when considering a configurational entropy contribution at 2000 K. Out of the 56 predicted stable phases, 32 displayed a preference for chemical order whereas 24 favored disorder of M ' and M ''. Initial attempts at synthesis of the predicted stable Ta2MoB2 compound were made, showing indications for the presence of ordered Ta2MoB2 or disordered (Ta0.667Mo0.333)3B2.