The corrosion resistance and mechanical properties of nanocrystalline aluminium (Al) and Al-20. wt.%Cr alloys, synthesized by high-energy ball milling followed by spark plasma sintering, were investigated. Both alloys exhibited an excellent combination of corrosion resistance and compressive yield strength, which was attributed to the nanocrystalline structure, extended solubility, uniformly distributed fine particles, and homogenous microstructure induced by high-energy ball milling. This work demonstrates the possibilities of developing ultra-high strength Al alloys with excellent corrosion resistance, exploiting conventionally insoluble elements or alloying additions via suitable processing routes.