For the first time, ceramic nano particles were incorporated into the brass alloy to produce surface nano composites by friction stir processing. For this aim, Al2O3 particles with an average diameter of 30 nm were inserted into a Cu-37Zn alloy at different tool rotational speeds of 450, 710, and 1120 rpm, multi passes, and a constant traverse speed of 100 mm/min. The microstructures of the processed materials were analyzed using optical and scanning electron microscopes equipped with an energy dispersive spectroscopy. In addition, tensile test was employed to evaluate the mechanical properties. The results showed that the optimum rotational speed was 710 rpm. At lower rotational speeds, Al2O3 particles were agglomerated. On the other hand, at higher rotational speeds, tool was damaged by severe wear. The effect of multi passes showed that one and two passes could not distribute the Al2O3 particles, uniformly. However, three passes resulted in a uniform distribution of the Al2O3 particles inside a bimodal grain structure composed of both 3–5 μm grains and ultra-fine grains (< 1 μm). By using multi-pass friction stir processing, a synergic increase in ultimate tensile strength and elongation was obtained. Moreover, three passes caused superior mechanical properties i.e. ultimate tensile strength of 430 MPa and elongation of 39%. The fracture behavior and strengthening mechanisms are also discussed in details.