Methods and apparatus for conditional deletes of storage objects are disclosed. A storage medium comprises program instructions that when executed, implement a metadata node of a storage service in which a protocol based on sequence numbers is used to resolve update conflicts. The instructions store, as part of a conditional deletion record associated with a key of a particular storage object identified as a deletion candidate, a deletion sequence number derived from a particular modification sequence number of the object. In accordance with the protocol, the instructions determine whether an additional modification sequence number larger than the deletion sequence number has been generated in response to an operation associated with the key. If such an additional sequence number has been generated, the deletion of the storage object is canceled.