In view of cooperative task allocation of Autonomous Underwater Vehicle (AUV), a Multi-Objective Discrete Particle Swarm Optimization and Simulated Annealing (MODPSO-SA) algorithm based on Pareto is proposed.In order to make the particle swarm optimization avoid from falling into local minimum, a new multi-objective local search strategy is proposed by integrating the improved simulated annealing.The simulation results show that the MODPSO-SA algorithm can obtain multiple Pareto solution sets, and solve the multi-AUV task allocation problem effectively.