The last prevision of the european Think Tank IDATE Digiworld estimates to 35 billion of connected devices in 2030 over the world just for the consumer market. This deep wave will be accompanied by a deluge of data, applications and services. Thus, it is quite urgent to propose operational Fog architectures that support low latency, mobility (of users and possibly infrastructure) and network partitioning. In this chapter, we will detail such an architecture that consists in coupling an object store system and a scale-out NAS (Network Attached Storage) allowing both scalability and performance. Moreover, we provide a new protocol inspired from the Domain Name System (DNS) to manage replicas in a context of mobility. Finally, we discuss the conceptual proximity between Fog storage, Content Delivery Networks (CDN) and Name Data Networking (NDN). A complete experimental evaluation is done over the French cluster Grid’5000 in a second part of the chapter.