Methods, apparatus, and computer-accessible storage media for providing a volume-based block storage service and application programming interfaces (APIs) to the service. A block storage service and block storage service APIs may allow processes (applications or appliances) on the service client network to leverage remote, volume-based block storage provided by the service provider. The APIs may provide a standard interface to volume-based block storage operations on a remote data store. The service provider, the service clients, and/or third parties may develop various applications and/or appliances that may, for example, be instantiated in service clients' local networks and that leverage the block storage service via the APIs to create and manage volumes and snapshots on the remote data store and to upload and download data from the volumes and snapshots on the remote data store.