Three heterostructured AlN_p/Al composites with different microstructure configurations were fabricated by liquid-solid reaction combined with subsequent thermal-mechanical treatment to obtain a superior strength and ductility combination. The effects of the microstructure configuration including the AlN particle distribution and matrix grain structure on the tensile strength and ductility were studied in detail. The results show that the simultaneous enhancement of tensile strength and ductility can be achieved. The Uniformed-AlN_p/Al composite with relatively dispersed particles exhibits a superior ultimate tensile strength of ~387 MPa with an elongation to failure of ~9.1%. It shows an outstanding specific tensile strength and elongation combination compared with other reported particle reinforced aluminum matrix composites. Furthermore, the hetero-deformation induced (HDI) stress has been calculated and is shown to increase significantly in the Uniformed-AlN_p/Al composite. It is revealed that the HDI stress plays a crucial role in the significant enhancement of strength and ductility for the AlN_p/Al composite.