1. A storage device configured to join a network-accessible storage service comprised of a plurality of unaffiliated storage nodes, the storage device comprising: a storage medium for electronically storing data; a network communication component for detecting a connection with a wide area network (WAN) and sending and receiving data via the WAN; a registration component coupled to the network communication component and configured to transmit a registration request across the WAN to a storage service management node, the registration request offering to associate at least a portion of the storage medium with a network-accessible storage service under terms that have no service level guarantee, the registration component receiving a confirmation from the storage service management node when the offer to associate at least a portion of the storage medium is accepted by the storage service management node; and an access manager coupled to the network communication component and configured to, after the registration component receives the confirmation from the storage service management node, receive data across the WAN from a client device that utilizes the network-accessible storage service, the access manager storing the received data in the storage medium, wherein the received data is encrypted prior to receipt so that the received data is not readily accessible to the host of the storage device.