Twin boundaries have been proven effective for strengthening metallic materials while maintaining plasticity. Al, however, has low twinning propensity due to its high stacking fault energy. Here we show, by using a small amount of Ni solutes, high-density twin boundaries and stacking faults in sputtered Al-Ni solid solution alloys. Density function theory calculations show that the Ni solute facilitates the formation of stacking faults and stabilizes nanotwins in Al-Ni solid solution alloys. In situ micropillar compression studies reveal a high flow stress (exceeding 1.7 GPa), comparable to high strength martensitic steels and Ni alloys. Furthermore, significant plasticity was observed in these nanotwinned Al-Ni alloy films due to the existence of high density twin boundaries and 9R phase.