Bulk nanocrystalline Al was fabricated by mechanically milling at cryogenic temperature (cryomilling) and then by hot pressing in vacuum. By using X-ray diffraction (XRD), scanning electron microscopy (SEM), and transmission electron microscopy (TEM), the microstructure evolution of the material during cryomilling and consolidation was investigated. With increasing the milling time, the grain size decreased sharply and reduced to 42 nm when cryomilled for 12 h. The grains had grown up, and the columnar grain was formed under the hot pressing and extrusion compared with the cryomilled powders. The grain size of as-extruded specimen was approximately 300-500 nm. The reason of high thermal stability of this bulk was attributed primarily to the Zener pinning from the grain boundary of the AlN arising from cryomilling and the solute drag of the impurity. Tensile tests show that the strength of nanocrystalline Al is enhanced with decreasing grain size. The ultimate tensile strength and tensile elongation were 173 MPa and 17.5%, respectively. It appears that the measured high strength in the cryomilled Al is related to a grain-size effect, dispersion strengthening, and dislocation strengthening.