CoAl-Al2O3 nanocomposite was produced by mechanical alloying (MA) of Co3O4-Al powder mixture. After 25 h MA, the grain size for CoAl and Al2O3 was found to be 19 and 26 nm, respectively (Table I). The resulting CoAl phase had an ordered structure with a long range order (LRO) parameter of 0.83. Subsequent annealing at different temperatures (Figures 1 and 2) causes three kinds of structural evolutions: reordering and disordering, strain relaxation and grain growth. Isothermal annealing at temperatures below 773K resulted in a fully ordered CoAl while at higher temperatures disordering occurred again. Decrease of LRO parameter at higher temperatures was interpreted to be due to the thermal activation, which induced triple defects [1]. The lattice strain of both CoAl and Al2O3 is rapidly reduced at first, and then reaches to a steady value, by increasing the temperature. Grain growth rate of constituent phases was observed to reduce at higher temperatures (Table I).