The increasing energy demands of modern society require a deep understanding of the properties of energy storage materials, as well as the tuning of their performance. We show that the capacitance of graphene oxide (GO) can be precisely tuned using a simple electrochemical reduction route. In situ resistance measurements, in combination with cyclic voltammetry measurements and Raman spectroscopy, have shown that upon reduction GO is irreversibly deoxygenated, which is further accompanied by structural ordering and an increase in electrical conductivity. The capacitance is maximized when the concentration of oxygen functional groups is properly balanced with the conductivity. Any further reduction and deoxygenation leads to a gradual loss of capacitance. The observed trend is independent of the preparation route and the exact chemical and structural properties of GO. It is proposed that an improvement in the capacitive properties of any GO can be achieved by optimization of its reduction conditions.