Methods to strengthen aluminum alloys have been employed since the discovery of the age-hardening phenomenon in 1901. The upper strength limit of bulk Al alloys is~ 0.7 GPa by conventional precipitation strengthening and increases to> 1 GPa through grain refinement and amorphization. Here we report a bulk hybrid nanostructured Al alloy with high strength at both room temperature and elevated temperatures. In addition, based on high-resolution transmission electron microscopic observations and theoretical analysis, we attribute the strengthening mechanism to the composite effect of the high-strength nanocrystalline fcc-Al and nano-sized intermetallics as well as to the confinement effect between these nano phases. We also report the plastic deformation of nano-sized intermetallics and the occurrence of a high density of stacking faults and twins in fcc-Al after low-strain-rate deformation at room and high temperatures. Our findings may be beneficial for designing high-strength materials for advanced structural applications.