Among the beyond Li-ion battery chemistries, nonaqueous Li-O$_2$ batteries have the highest theoretical specific energy and as a result have attracted significant research attention over the past decade. A critical scientific challenge facing nonaqueous Li-O$_2$ batteries is the electronically insulating nature of the primary discharge product, lithium peroxide, which passivates the battery cathode as it is formed, leading to low ultimate cell capacities. Recently, strategies to enhance solubility to circumvent this issue have been reported, but rely upon electrolyte formulations that further decrease the overall electrochemical stability of the system, thereby deleteriously affecting battery rechargeability. In this study, we report that a significant enhancement (greater than four-fold) in Li-O$_2$ cell capacity is possible by appropriately selecting the salt anion in the electrolyte solution. Using $^7$Li nuclear magnetic resonance and modeling, we confirm that this improvement is a result of enhanced Li$^+$ stability in solution, which in turn induces solubility of the intermediate to Li$_2$O$_2$ formation. Using this strategy, the challenging task of identifying an electrolyte solvent that possesses the anti-correlated properties of high intermediate solubility and solvent stability is alleviated, potentially providing a pathway to develop an electrolyte that affords both high capacity and rechargeability. We believe the model and strategy presented here will be generally useful to enhance Coulombic efficiency in many electrochemical systems (e.g. Li-S batteries) where improving intermediate stability in solution could induce desired mechanisms of product formation.