This letter investigates the localization problem with distance-dependent noise and sensor location uncertainty. The formulated localization problem is very challenging and non-convex due to the coupled distance-dependent noise variance and the location uncertainty, as well as the nonlinearity in the distance function. A low complexity two-step algorithm that incorporates maximum likelihood and Gaussian message passing (ML-GMP) algorithms is proposed to estimate the target location. It first transforms the distance-dependent noise into distance-independent one by introducing the distance as an intermediate parameter and adopting ML criterion for estimation. A low complex GMP algorithm is then followed to deal with the sensor location uncertainties and estimate the target location. Convergence of the proposed algorithm is proved, and simulation results show the proposed ML-GMP algorithm can approach the Bayesian Cramer-Rao bound (BCRB) and outperforms the other existing algorithms.