Techniques for effective delete operations in a distributed data store with eventually consistent replicated entries include determining to delete a particular entry from the distributed data store. Each entry includes a first field that holds data that indicates a key and a second field that holds data that indicates content associated with the key and a third field that holds data that indicates a version for the content. The method also comprises causing, at least in part, actions that result in marking the particular entry as deleted without removing the particular entry, and updating a version in the third field for the particular entry.