The work aims to find optimal machining parameters by studying the process of milling 45# steel with abrasive water jet which takes surface roughness and material removal rate as output parameters. Material removal mechanism was analyzed, Tian orthogonal experiment with abrasive particle size, jet pressure, transverse feed velocity, target distance as machining process parameters was designed and performed. Minitab was used to analyze surface roughness and material removal efficiency of 45# steel subject to abrasive water jet machining in different experimental parameter combinations, impact and impact trend of the 4 machining process parameters on milled surface quality and material removal efficiency from the aspect of material removal mechanism, and interaction among different factors. Transverse feed distance had the most significant effect on jet milled surface roughness, jet pressure took the second place. Abrasive particle size had the most significant effect on material removal efficiency, transverse feed distance took the second place. The optimal machining parameters are selected as follows by allowing for material removal efficiency and surface roughness: abrasive particle size of 2000#, jet pressure of 120~160 MPa, nozzle sidesway distance of 1.0~1.5 mm and target distance of about 30 mm.