The North Natuna Sea has high strategic and economic importance because it is an important trade route and has abundant fishery resources. However, the region is prone to illegal fishing and border violations. In 2020-2022, there were 162 violations, while 2023 recorded 14 warship contacts. The Indonesian Navy has organized security operations with warships and maritime patrol aircraft. However, budget constraints are a major obstacle. Autonomous vehicles are a potential solution due to their lower cost, high efficiency, and advanced monitoring capabilities. This research aims to determine the priorities and criteria of Autonomous vehicles suitable for patrolling the North Natuna Sea. This research uses a quantitative method with Analytic Network Process (ANP) to analyze the relationship between system elements. The data was analyzed with a Multi Criteria Decision Making approach using Super Decision version 3.10 software to generate objective decisions. The main criteria included Performance, Operational, Maintenance, and Cost. The ANP model allows the evaluation of interrelated factors, determining the priority of Autonomous Vehicles in patrolling the North Natuna Sea. The results showed that the main criteria in the selection of Autonomous Vehicles for patrolling in the North Natuna Sea were Performance (0.441), followed by Cost (0.267), Operational (0.181), and Maintenance (0.111). At the sub-criteria level, Endurance has the highest priority (0.151), followed by Acquisition Cost (0.118) and Range (0.098). For vehicle alternatives, UAV ranked first (0.509), followed by AUV (0.281), UCAV (0.136), and USV (0.074). These results show that UAV is the best choice for maritime patrol based on the factors of performance, cost, and operational range.