The rechargeable aprotic lithium-air (Li-O2) battery is a promising potential technology for next-generation energy storage, but its practical realization still faces many challenges. In contrast to the standard Li-O2 cells, which cycle via the formation of Li2O2, we used a reduced graphene oxide electrode, the additive LiI, and the solvent dimethoxyethane to reversibly form and remove crystalline LiOH with particle sizes larger than 15 micrometers during discharge and charge. This leads to high specific capacities, excellent energy efficiency (93.2%) with a voltage gap of only 0.2 volt, and impressive rechargeability. The cells tolerate high concentrations of water, water being the dominant proton source for the LiOH; together with LiI, it has a decisive impact on the chemical nature of the discharge product and on battery performance.