With the rapid development of Autonomous Underwater Vehicles (AUVs) and Unmanned Surface Vessels (USVs) in both civil and military domains, the collaboration between USVs and AUVs for performing certain tasks has attracted widespread attention. This paper focuses on the task assignment problem for multiple USVs and AUVs to visit multiple target locations, aiming to minimize the total travel distance for multiple USVs and AUVs to visit all target locations. Firstly, a mathematical model for the studied task assignment problem is established, considering the AUVs’ communication constraints and the maximum travel distance, and the NP-hardness of the problem is analyzed. Secondly, a two-stage task assignment algorithm is proposed: 1) The initial routes of the USVs to visit all the surface target locations are first constructed using the Minimum Marginal-cost Algorithm, and the nearest insertion strategy is adopted to assign underwater target locations? 2) The initial assignment solution is improved through several neighborhood search operators. Simulation results show that the proposed algorithm can obtain a better assignment solution within a shorter running time than the existing popular self-organizing map algorithm.