An object-backed block-based storage system may store data blocks in a block cache in a non-relational database and data block objects in an object data store. Access requests for a particular data block may be received at a storage protocol target that are formatted according to a network-based storage protocol. Translated access requests formatted according to respective programmatic interfaces may be generated and sent to the non-relational database or to the object data store in order to access the particular data block. A response indicating success or failure of the access request may be sent.