AlB2-type TaB2 is one of the transition-metal diborides, a class of refractory ceramics, that has increasingly received attention due particularly to their potential for hard-coating applications. In this work, the first-principles calculations are performed, in combination with the cluster-expansion method, to investigate the effect of mixing AlB2 with TaB2 on the thermodynamic stability, structural parameters, electronic density of states, and mechanical behavior of the resulting (Ta,Al)B-2 solid solutions. It is found that the solid solutions display the chemical ordering of Ta and Al atoms both residing on the metal sublattice of the material, together with the preference for partial substitution of vacancies for Al atoms. This results in the formation of Al-deficient (Ta,Al)B-2 with the chemical composition Ta0.6Al0.3B2, predicted to be thermodynamically stable even at absolute zero in the ternary Ta-Al-B system. It is further found that such formation of Al vacancies in (Ta,Al)B-2 not only enhances the stability of the solutions but also improves their elastic properties and hardness, both of which could be attributed to the effect of electronic band filling. This investigation indeed sheds light on the interplay between the mixing of Ta and Al atoms and the presence of Al vacancies on the alloying and mechanical behaviors of (Ta,Al)B-2, and it thus offers valuable insights for further research and development of these ceramics.