Crystal structure prediction of new ternary compounds is challenging due to a very large chemical space with many possible compositions, few of which turn out to be stable. Using the evolutionary algorithm USPEX, here we predicted potentially superhard ternary compounds in the W-Mo-B system. Five new stable ternary compounds with various chemical compositions were predicted at different temperatures, and the composition-temperature phase diagrams were calculated. Electronic properties of the new compounds were studied in detail to find their correlation with the mechanical properties, crystal structure, and atomic composition (i.e., mass percentage of elements within the molecular formula).