A network-based data store may implement retention-based management techniques for data stored at the network-based data store. When data is received for storage at the network-based data store, a retention time for the data may be determined. Storage locations at persistent storage devices of the network-based data store may be selected according to the retention time. The data may then be placed at the storage locations. When a request to delete data is received, retention times of co-located data may be evaluated to determine whether the deletion may be delayed. Delayed deletions may allow the data to be subsequently deleted with at least some of the co-located data. Repair operations to maintain the data according to a durability policy may be modified according to retention time for a data suffering a loss of redundancy.