Machining of Titanium alloys (Ti6Al4V) becomes more vital due to its essential role in biomedical, aerospace, and many other industries owing to the enhanced engineering properties. In the current study, a Box-Behnken design of the response surface methodology (RSM) was used to investigate the performance of the abrasive water jet machining (AWJM) of Ti6Al4V. For process parameter optimization, a systematic strategy combining RSM and a heat-transfer search (HTS) algorithm was investigated. The nozzle traverse speed (T ), abrasive mass flow rate (A ), and stand-off distance (S ) were selected as AWJM variables, whereas the material removal rate (MRR), surface roughness (SR), and kerf taper angle (θ) were considered as output responses. Statistical models were developed for the response, and Analysis of variance (ANOVA) was executed for determining the robustness of responses. The single objective optimization result yielded a maximum MRR of 0.2304 g/min (at T of 250 mm/min, A of 500 g/min, and S of 1.5 mm), a minimum SR of 2.99 µm, and a minimum θ of 1.72 (both responses at T of 150 mm/min, A of 500 g/min, and S of 1.5 mm). A multi-objective HTS algorithm was implemented, and Pareto optimal points were produced. 3D and 2D plots were plotted using Pareto optimal points, which highlighted the non-dominant feasible solutions. The effectiveness of the suggested model was proved in predicting and optimizing the AWJM variables. The surface morphology of the machined surfaces was investigated using the scanning electron microscope. The confirmation test was performed using optimized cutting parameters to validate the results.