Aiming to solve the search problem of geomagnetic multi-component and multiobjective, the multi-objective evolutionary search algorithm based on the magneto-taxis sensitivity was proposed for the autonomous underwater vehicles. Combined with the structure of the evolutionary algorithm, this method utilized the restrictive correlation between the geomagnetic components and the navigation path, and the magneto-taxis sensitivity was expressed as a posteriori assessment criteria to establish the navigation model. The geomagnetic multi-component converged to desired value along with the motion of the vehicle at the same time and place, thus realized the navigation goal. Compared with the hex-path searching algorithm, the effectiveness and advantages of the proposed algorithm were validated by the simulation experiments.