Knowledge of the physical locations of mobile devices such as laptops or PDA’s is becoming increasingly important with the rise of location-based services such as specialized web search, navigation, and social network applications; furthermore, location information is a key foundation for high-level activity inferencing. In this paper we propose a novel technique for accurately estimating the locations of mobile devices and their wearers from wireless signal strengths. Our technique estimates time-varying device locations on a spatial connectivity graph whose outdoor edges correspond to streets and whose indoor edges represent hallways, staircases, elevators, etc. Use of a hierarchical Bayesian framework for learning a signal strength sensor model allows us not only to achieve higher accuracy than existing approaches, but to overcome many of their limitations. In particular, our technique is able to (1) seamlessly integrate new access points into the model, (2) make use of negative information (not detecting an access point), and (3) bootstrap a sensor model from sparse training data. Experiments demonstrate various properties of our system.