New Co- and Al-substituted manganese dioxide materials have been prepared by electrochemical synthesis under hydrothermal conditions. The hollandite (α), pyrolusite (β) and γ structures can be stabilized using different experimental conditions. For each structure, the substitution leads to nanostructured compounds with various morphologies made of nanosized crystals and to much larger surface areas. Some substituted compounds display larger reversible Li insertion capacities than their non-substituted parents compounds.