Distinct differences in the nucleation of Al at room temperature on arsenic‐stabilized (2×4)‐ andc(4×4)‐GaAs(001) surfaces grown by molecular‐beam expitaxy have been observed with reflection high‐energy electron diffraction. The nucleation of Al is found to be dependent upon the amount of disorder on the (2×4)‐GaAs(001) surface. Phase diagrams showing the MBE growth parameters required for the preparation of more ordered versus more disordered surfaces of GaAs(001) have been constructed. The presence of disorder has been found to be independent of the rate of cooling of the GaAs substrate to room temperature for Al deposition. Nucleation on the more‐disordered (2×4) surface and on thec(4×4) surface are similar in the direction of twofold periodicity, but differ in the direction of fourfold periodicity. The presence of a strong Al metal adatom–adatom interaction of submonolayer coverages, formerly reported for Al/(2×4)‐GaAs(001), may help to explain why the more‐ordered (2×4)‐reconstructed surface preferentially nucleates fcc Al(110).