The many applications of high energy storage devices have forged an increasing interest in research areas related to electrochemical capacitors. Here, in this work, we present a facile method for the fabrication of self-organized titania nanotubes grown by anodic oxidation of titanium foil with different subsequent heat-treatment regimes for use as binder-free working electrodes in supercapacitor applications. The capacitance of these highly ordered titania nanotubes, when exposed to a reductive atmosphere during annealing, was determined to be well above 900 µF cm−2, confirming that the capacitance contribution was pseudocapacitive in nature. The behaviour of oxygen depleted titania in the anatase to rutile (A → R) phase transformation and also in electrochemical charge storage has been studied in detail. It was found that upon the reduction of Ti4+ to Ti3+, with oxygen depletion of the structure, the A → R phase transformation was promoted. In addition, the fabricated electrodes showed highly reversible charge–discharge stability.