In this study, a nano-composite material of a nanostructured Al-based matrix reinforced with Fe40Al intermetallic particles was produced by ball milling. During the non-equilibria processing, the powder mixtures with the compositions of Al-XFe40Al (X = 5, 10, and 15 vol. %) were mechanically milled under a low energy regime. The processed Al-XFe40Al powder mixtures were subjected to uniaxial pressing at room temperature. Afterward, the specimens were subjected to a sintering process under an inert atmosphere. In this thermal treatment, the specimens were annealed at 500 °C for 2 h. The sintering process was performed under an argon atmosphere. The crystallite size of the Al decreased as the milling time advanced. This behavior was observed in the three specimens. During the ball milling stage, the powder mixtures composed of Al-XFe40Al did not experience a mechanochemical reaction that could lead to the generation of secondary phases. The crystallite size of the Al displayed a predominant tendency to decrease during the ball milling process. The microstructure of the consolidated specimens indicated a uniform dispersion of the intermetallic reinforcement phases in the Al matrix. Moreover, according to the Vickers microhardness tests, the hardness varied linearly with the increase in the concentration of the Fe40Al intermetallic phase present in the composite material. The presented graphs indicate that the hardness increased almost linearly with the increasing dislocation density and with the reduction in grain sizes (both occurring during the non-equilibria processing). The microstructural and mechanical properties reported in this paper provide the aluminum matrix composite materials with the ideal conditions to be considered candidates for applications in the automotive and aeronautical industries.