The mechanical properties of metallic nanowires depend dramatically on the atmospheric conditions. Molecular-dynamics simulations with ReaxFF were conducted to study tensile elastic deformation of oxidized Al nanowires. The thin amorphous oxide shell formed around Al nanowires had a very low Young's modulus of 26 GPa, due to its low density and low Al-O coordination. Consequently, for diameters less than 100 nm, the composite Young's modulus of oxide-covered Al nanowires showed a size dependence implying that in this case “smaller is softer.” The model developed also explained the discrepancies in the reported modulus values of nanometer-scale Al thin films.