Phase diagrams for multi-component systems represent crucial information for understanding and designing materials but are very time consuming to assess experimentally. Computational modeling plays an increasingly important role in this regard but has been largely focused on systems with matching lattice structures and/or stable boundary phases. Here, using a combination of density functional theory calculations, alloy cluster expansions, free energy integration, and Monte Carlo simulations, we obtain the phase diagram of W-Ti, a system that features metastable boundary phases on both sides of the phase diagram. We find that the mixing energy on the body-centered cubic (BCC) lattice is asymmetric and negative with a minimum of about -120 meV/atom, whereas for the hexagonal closed packed (HCP) lattice the mixing energy is positive. By combining these data with a model for the vibrational free energy, we propose a revision of the W-rich end of the phase diagram with a much larger solubility of Ti in BCC-W than previous assessments. Finally, by comparison with the W-V and W-Re system we demonstrate how strongly asymmetric phase diagrams can arise from a subtle energy balance of stable and metastable lattice structures.