A growing number of mobile phone applications utilize physical location to express the context of information. Most of these location-based applications assume GPS capabilities. Unfortunately, GPS incurs an unacceptable energy cost that can reduce the phone's battery life to less than nine hours. Alternate localization technologies, based on WiFi or GSM, improve battery life at the expense of localization accuracy. This paper quantifies this important tradeoff that underlies a range of emerging services. Driven by measurements from Nokia N95 phones, we develop an energy-efficient localization framework called EnLoc. The framework characterizes the optimal localization accuracy for a given energy budget, and develops prediction- based heuristics for real-time use. Evaluation on traces from real users demonstrates the possibility of achieving good localization accuracy for a realistic energy budget.