Recently, it has been found that mechanical alloying (MA) facilitates the nanocomposites formation of metal-metal oxide systems through solid-state reduction during ball milling. In this work, we studied the MA effect of Fe_3O_4-M (M = Al, Ti) systems, where pure metals are used as reducing agents. It is found that composite powders in which Al_2O_3 and TiO_2 are dispersed in alpha-Fe matrix with nano-sized grains are obtained by mechanical alloying of Fe_3O_4 with Al and Ti for 25 and 75 hours, respectively. It is suggested that the large negative heat associated with the chemical reduction of magnetite by aluminum is responsible for the shorter MA time for composite powder formation in Fe_3O_4-Al system. X-ray diffraction results show that the reduction of magnetite by Al and Ti if a relatively simple reaction, involving one intermediate phase of FeAl_2O_4 or Fe_3Ti_3O_10. The average grain size of alpha-Fe in Fe-TiO_2 composite powders is in the range of 30 nm. From magnetic measurement, we can also obtain indirect information about the details of the solid-state reduction process during MA.