Nanocomposite formation of metal-metal oxide systems by mechanical alloying (MA) has been investigated at room temperature. The systems we chose are the Fe3O4-M (M=Al, Ti), where pure metals are used as a reducing agent. It is found that nanocomposite powders in which Al2O3 and TiO2 are dispersed in a α-Fe matrix with nano-sized grains are obtained by MA of Fe3O4 with Al and Ti for 25 and 75 hours, respectively. It is suggested that the shorter MA time for the nanocomposite formation in Fe3O4-Al is due to a large negative heat associated with the chemical reduction of magnetite by aluminum. X-ray diffraction results show that the average grain size of α-Fe in Fe-TiO2 nanocomposite 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.