All-vanadium redox flow batteries have attracted considerable interest as promising electrical energy storage devices, because of their ability to store large amounts of energy and to resist fluctuating power supplies. A crucial parameter for battery efficiency is the solubility of vanadium in the electrolyte solutions. Recently, it has been shown that sulfate-chloride mixed electrolytes increase vanadium solubility. In this work, we identify the most stable complexation structures in this improved electrolyte, by means of ab initio molecular dynamics together with the well-tempered metadynamics algorithm. We characterize the first solvation shell of vanadium cations in solution and estimate the free energy difference of all of the configurations. Our results suggest that chloride ions play an important role in stabilizing V(II), V(III), and V(V) species. In the specific case of V(V), we find that the most stable configuration exhibits a simultaneous complexation operated by chloride and sulfate ions, suggesting possible strategies to design novel agents to prevent the precipitation of the vanadium cation.