In this paper, we employ compressive sensing (CS) to design a distributed compressive data storage (CStorage) algorithm for wireless sensor networks (WSNs). First, we assume that no neighbor information or routing table is available at nodes and employ the well-known probabilistic broadcasting (PB) to disseminate sensors reading throughout the network to form compressed samples (measurements) of the network readings at each node. After the dissemination phase, a data collector may query any arbitrary set of M ≪ N nodes for their measurement and reconstruct all N readings using CS. We refer to the first implementation of CStorage by CStorage-P. Next, we assume that nodes collect two-hop neighbor information and design a novel parameterless and scalable data dissemination algorithm referred to by alternating branches (ABs), and design CStorage-B. We discuss the advantages of CStorage-P and CStorage-B and show that they considerably decrease the total number of required transmissions for data storage in WSNs compared to existing work.