The use of three-axis magnetic sensor array to locate underwater ferromagnetic target is a typical nonlinear least squares optimization problem. Traditional Gaussian-Newton method (GN) and Levenberg-Marquardt (LM) algorithm have an initial sensitivity problem when solving this problem. This paper improves the LM algorithm by introducing the trust domain search technology, and realizes magnetic target localization based on the improved LM algorithm, then the distance between the iteration point and the optimal solution is evaluated by setting the threshold value, and proposes an improved LM-GN algorithm combining the characteristics of the improved LM algorithm and Gaussian-Newton method. It not only reduces the dependence of the algorithm on the initial value, but also improves the operation efficiency. The simulation results show that the proposed method can overcome the problem of the existing methods which are greatly affected by the initial value, and the estimation of the target characteristic parameters is more accurate and the convergence rate is fast, so it has certain practical application value.