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$_{3}$O$_{4}$-M (M = Al, Ti) systems, where pure metals are used as reducing agents. It is found that composite powders in which $Al_{2}$O$_{3}$ and TiO$_{2}$ are dispersed in $alpha$-Fe matrix with nano-sized grains are obtained by mechanical alloying of Fe$_{3}$O$_{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$_{3}$O$_{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$_{2}$O$_{4}$ or Fe$_{3}$Ti$_{3}$O$_{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.