Mobile Cloud Storage (MCS) systems – cloud storageon mobile devices without access to remote data center-type cloud resources, are not only interesting from a theoretical point of view, as they pose the most challenging design settings, but also important in enabling real-world applications such as disaster relief, military operation, and mining in remote areas. Central to MCS design is how to minimize the energy consumption of the battery-powered devices while still maintaining the data reliability and availability. Unfortunately, existing solutions do not model the energy-efficiency and data reliability of MCS in an integrated manner. Their formulations predominantly makeuse of heuristics, which may over-emphasize energy efficiency and not provide sufficient data reliability for some applications. In this paper, we design an energy-efficient distributed data storage framework in MCS under explicit data reliability requirement. The novel formulations produce a reliability-compliant and energy-efficient MCS system. The performance characteristics of our solutions are extensively evaluated through both real-world and synthetic mobility traces.