We describe a comprehensive ab initio investigation of phase stability and mechanical properties of W-Ta and W-V alloys, which are candidate materials for fusion power plant applications. The ab initio density functional calculations compare enthalpies of mixing for alternative ordered atomic structures of the alloys, corresponding to the same chemical composition. Combining the ab initio data with large-scale lattice Monte-Carlo simulations, we predict several low-energy intermetallic compounds that are expected to dominate alloy microstructures, and hence the low-temperature phase diagrams, for both alloys. Using the predicted ground-state atomic alloy configurations, we investigate the short-range order, point defect (vacancy and self-interstitial atoms) energies, and thermodynamic and mechanical properties of W alloys as functions of their chemical composition. In particular, we evaluate the anisotropic Young modulus for W-Ta and W-V alloys from ab initio elastic constant calculations, with the objective of comparing the predicted values with experimental micro-cantilever measurements. Also, using the calculated Poisson ratios for binary W alloys, which combine tungsten with more than 40 different alloying elements, we investigate if alloying improves the ductility of tungsten-based materials.