Changes in hardness of Fe-40Al powders during milling and during subsequent annealing have been examined and related to the many structural changes occurring. During milling, the material becomes significantly disordered with a small domain size and many vacancies, and refines to a nano-scale grain size, while on subsequent annealing at progressively higher temperatures these structural defects are lost as the material re-orders, loses point defects and as the grains grow to large sizes. The increase in hardness during milling can be explained by the combined contributions of vacancy hardening, ordered domain/particle hardening, and by disorder hardening within the ordered regions. Softening during annealing occurs as the domain/particle hardening, disorder hardening and vacancy hardening are successively lost. Dislocation-induced work hardening and grain size hardening are believed to play only minor roles in affecting the material hardness.