A precise range difference (RD)-based passive target localization algorithm is proposed for mobile robot applications. To effectively solve the real-time issue, the nonlinear relation between the RD information and the target location is removed by introducing the target range as an auxiliary variable to be estimated. Then, the RD-based localization problem is formulated in the setting of linear estimation. The resultant linear measurement model contains the stochastic parametric uncertainty which causes the severe performance degradation of the conventional linear least squares (LS) method when the RD measurement noise is not negligible. To cope with this problem, the recently developed linear robust LS (RoLS) estimation theory is applied for the passive target localization problem. Using the geometric relation among the ultrasonic receivers, a systematic way to determine the design parameters of the RoLS estimator is suggested. It is shown that the proposed method can provide the nearly unbiased target location estimates for the whole location area. The proposed solution is very practical because it is preferable for real-time robot applications owing to its linear recursive structure. Through the computer simulations and actual experiments, it is shown that the proposed algorithm guarantees the superior localization performance and the fast convergence compared to the existing one.