Existing localization algorithms, such as centroid or finger-printing, compute the location of a mobile device based on measurements of signal strengths from radio base stations. Unfortunately, these algorithms require tedious and expensive off-line calibration in the target deployment area before they can be used for localization. In this paper, we present Calibree, a novel localization algorithm that does not require off-line calibration. The algorithm starts by computing relative distances between pairs of mobile phones based on signatures of their radio environment. It then combines these distances with the known locations of a small number of GPS-equipped phones to estimate absolute locations of all phones, effectively spreading location measurements from phones with GPS to those without. Our evaluation results show that Calibree performs better than the conventional centroid algorithm and only slightly worse than fingerprinting, without requiring off-line calibration. More-over, when no phones report their absolute locations, Calibree can be used to estimate relative distances between phones.