This paper presents a hypothesis and its experimental validation that simultaneous improvement in the hardness and corrosion resistance of aluminium can be achieved by the combination of suitable processing route and alloying additions. More specifically, the corrosion resistance and hardness of Al- xCr (x= 0-10 wt.%) alloys as produced via high-energy ball milling were significantly higher than pure Al and AA7075-T651. The improved properties of the Al- xCr alloys were attributed to the Cr addition and high-energy ball milling, which caused nanocrystalline structure, extended solubility of Cr in Al, and uniformly distributed fine intermetallic phases in the Al-Cr matrix.