Herein, we report the facile synthesis of two alpha-Fe2O3 nanostructures with different morphologies via an electrospinning technique using ferric acetyl acetonate as a precursor and polyvinyl acetate and polyvinyl pyrrolidone as the respective polymers. The as-electrospun metal oxide-polymer composite fibers were sintered at 500 degrees C to obtain two distinct nanostructures, denoted as nanograins and porous fibers throughout this manuscript. These crystalline nanostructures were characterized using powder X-ray diffraction (XRD), Raman spectroscopy, scanning electron microscopy (SEM), energy dispersive X-ray spectroscopy (EDAX) and transmission electron microscopy (TEM). The characterization results elucidated the predominance of hematite (alpha-Fe2O3) with particle sizes of 21 and 53 nm, for the respective nanostructures. Electrophoretic deposition was carried out in order to fabricate thin film electrodes, which were then subjected to electrochemical analysis. Electrochemical characterization revealed that both of the fabricated electrodes exhibited excellent performance in 1 M LiOH electrolyte with specific capacitance values of 256 and 102 F g(-1) for the porous fiber and nanograin structures, respectively, at a scan rate of 1 mV s(-1) and excellent capacitance retention, even after 3000 cycles, thus making them promising electrode materials for energy storage devices.