Pronounced and stable pseudocapacitance has been found in flowerlike FeTiO3 nanostructures that were synthesized from ball-milled ilmenite (natural mineral) under mild hydrothermal conditions. Each nanoflower is composed of many thin petals with a thickness of 5–20 nm and a width of 100–200 nm. The formation of these flowerlike nanostructures is attributed to a dissolution–precipitation mechanism involving an intermediate sodium-containing phase. Electrochemical properties of the obtained FeTiO3 nanostructures are evaluated in aqueous electrolytes. The capacitance of 122 ± 14.5 F/g is measured in 1 M KOH aqueous electrolyte at the current rate of 500 mA/g, and 50 ± 6 F/g is retained at 5 A/g. The material has good long-term cycling stability. According to our data, FeTiO3 nanostructures show functionality as an electrode material for supercapacitors.