We have developed a new on-line error modeling and optimization-based localization approach for sensor networks in the presence of distance measurement noise. The approach is solely based on the concept of consistency, and is developed specifically for the case of on-line localization, which refers to the situation when references are not available a priori. The localization problem is formulated as the task of maximizing the consistency between measurements and calculated distances. In addition, we also present a localized localization algorithm where a specified communication cost or the location accuracy is guaranteed while optimizing the other. We evaluated the approach in (i) both GPS-based and GPS-less scenarios; (ii) 1-D, 2-D and 3-D spaces, on sets of acoustic ranging-based distance measurements recorded by deployed sensor networks. The experimental evaluation indicates that localization of only a few centimeters is consistently achieved when the average and median distance measurement errors are more than a meter, even when the nodes have only a few distance measurements. The relative performance in terms of location accuracy compares favorably with respect to several state-of-the-art localization approaches. Finally, several insightful observations about the required conditions for accurate location discovery are deduced by analyzing the experimental results.