Rock-salt scandium nitride has gained interest due to its thermoelectric properties including a relatively high Seebeck coefficient. This motivates research for other semiconductor materials that exhibit similar electronic structure features as ScN. Using density functional theory calculations, we have studied disordered solid solutions of (Zr-0.5, Mg-0.5)N and (Hf-0.5, Mg-0.5)N using the special quasi-random structure model. The results show that within a mean-field approximation for the configurational entropy, the order-disorder phase transformation between the monoclinic LiUN(2)prototype structure and the rock-salt cubic random alloy of these mentioned solid solutions occur at 740 K and 1005 K for (Zr-0.5, Mg-0.5)N and (Hf-0.5, Mg-0.5)N, respectively. The density-of-states for the two ternary compounds is also calculated and predicts semiconducting behavior with band gaps of 0.75 eV for (Zr-0.5, Mg-0.5)N and 0.92 eV for (Hf-0.5, Mg-0.5)N. The thermoelectric properties of both compounds are also predicted. We find that in the range of a moderate change in the Fermi level, a high Seebeck coefficient value at room temperature can be achieved.