Ultrafine-grained (UFG) and nanostructured (NS) materials have attracted considerable interest due to their special microstructure and mechanical properties. Severe plastic deformation is one of the optimum approaches to fabricate bulk, dense and contamination-free UFG and NS metallic materials. However, high density of dislocations and unstable microstructure were usually induced in these UFG and NS metallic materials, resulting in poor tensile plasticity and fatigue properties. In this study, bulk UFG and NS Cu-Al alloys were successfully prepared via friction stir processing (FSP) with additional forced water cooling. FSP Cu-Al alloys exhibited uniform recrystallized microstructure with equiaxed ultrafine grains, and the grain sizes reduced gradually as the stacking fault energy (SFE) decreased. Abundant nano-twin layers formed in the ultrafine grains of FSP Cu-Al alloys with low SFEs, which further refined the ultrafine grains and NS microstructure was achieved. The strength of the FSP Cu-Al alloys increased clearly with decreasing the SFEs due to the gradually refined microstructure, but the uniform elongation increased initially and then decreased in the Cu-Al alloy with the lowest SFE.