We have designed and synthesized a novel nanocrystalline manganese oxide with a nanofibrous morphology by employing an electrodeposition process in the presence of a non-ionic surfactant. This unique nanoporous/nanocrystalline material effectively accommodates the structural transformation during lithium insertion and avoids deleterious morphological changes as observed in battery materials composed of large particles. Consequently, the material exhibits outstanding cycling stability in addition to its high discharge capacity.