A series of Ni-M (M = Cu, Fe, Mo)-based alloys is synthesized using mechanochemical alloying of metal powders. The phase composition and structure of Ni-M samples are analyzed by powder X-ray diffraction. The catalytic activity of Ni-M B is studied in the synthesis of carbon nanofibers (CNFs) by decomposing a C2H4Cl2/H2/Ar mixture at 600 °C. It is shown that as a result of the interaction of alloys with the reaction medium, their rapid disintegration occurs with the formation of active particles catalyzing the growth of CNFs. The highest yield (22.2 g(CNF)/g(Ni)) is obtained for Ni-Mo alloy (in 2 h). The structural and morphological features of carbon materials are investigated. SEM and TEM data indicate the formation of carbon fibers with a pronounced segmented structure. The specific surface of the carbon material is 250–400 m2/g.