We have investigated Mg intercalation into orthorhombic V$_2$O$_5$, one of only three cathodes known to reversibly intercalate Mg ions. By calculating the ground-state Mg$_x$V$_2$O$_5$ configurations and by developing a cluster expansion for the configurational disorder in δ-V$_2$O$_5$, a full temperature–composition phase diagram is derived. Our calculations indicate an equilibrium phase-separating behavior between fully demagnesiated α-V$_2$O$_5$ and fully magnesiated δ-V$_2$O$_5$, but also motivate the existence of potentially metastable solid solution transformation paths in both phases. We find significantly better mobility for Mg in the δ polymorph, suggesting that better performance can be achieved by cycling Mg in the δ phase.