The Mn-C-O composites were synthesized by the electric-arc discharge method. The composite materials were obtained by spraying of graphite electrode with the addition of MnO2. The morphology of Mn-C-O composites formed during electric-arc spraying of metal-carbon electrodes in various buffer gases (N2 and He) and the effect of their subsequent annealing in an oxygen-containing atmosphere was studied. It was experimentally determined that MnOx (MnO, Mn3O4) nanoparticles are mainly formed in N2 atmosphere, and Mn7C3 carbide nanoparticles are formed in He atmosphere. This phenomenon is explained by different cooling rates of the formed composites. With further annealing of materials, partial oxidation of nanoparticles and graphitization of the carbon matrix occur due to the thermal effect of the oxidation reaction. According to the study of electrochemical activity of materials in the 1 M KOH aqueous electrolyte, the materials with a higher MnO content and a higher degree of soot graphitization have the highest electrochemical capacity of 135 Fg−1.