The structure and phase stability of binary tungsten-vanadium and tungsten-tantalum alloys are investigated over a broad range of alloy compositions using ab initio and cluster expansion methods. The alloys are characterized by the negative enthalpy of mixing across the entire composition range. Complex intermetallic compounds are predicted by ab initio calculations as the lowest energy structures for both alloys. The effect of atomic relaxation on the enthalpy of mixing is almost negligible in W-V, but is substantial in W-Ta alloys. Canonical Monte Carlo simulations are used for predicting the order-disorder transition temperatures for both alloys. Differences in the short-range order between the two alloys are explained by the opposite signs of the second nearest-neighbour cluster interaction coefficients for W-V and W-Ta. Using the predicted ground-state structures, we evaluate the monovacancy formation energies and show that in W-Ta alloys they are highly sensitive to the alloy composition and the local environment of a vacancy site, varying from 3 to 5 eV. In the dilute tungsten alloy limit, a self-interstitial atom crowdion defect forms a configuration strongly bound to a vanadium solute atom, whereas interaction between the same defect and a tantalum solute atom is repulsive. Values of elastic constants computed for all the ground-state structures and several metastable cubic alloy structures are used for assessing the effect of alloying on mechanical properties. Values of the Young modulus and the Poisson ratio, as well as the empirical Rice-Thompson criterion, are applied to screening the alloys, to assess the effect of chemical composition on ductility.