In recent years, two major trends have changed the way mobile phones are used: smartphones have become a plat- form for applications, and 3G connectivity has turned them into ubiquitous Internet clients. Increasingly, applications on smartphones (such as document sharing, media players and map browsers) interact with the cloud as a backend for data storage and computation. We observe that, for many mobile applications, the specific data that is accessed depends on the current location of the user. For example, a restaurant recommendation application is often used to get information about nearby restaurants. In this paper, we present WhereStore, a location-based data store for smartphones interacting with the cloud. It uses filtered replication along with each device’s location history to distribute items between smartphones and the cloud. We discuss the challenges of designing such a system, relevant applications, and a specific design and prototype implementation.