A storage system includes a secondary data store for backing up the primary data store, a deleted data store for retention of deleted data, and a data management application for managing the backing up of stored and deleted data of the primary data store. The deleted data store may be either separate from the secondary data store or implemented within the secondary data store. The data management application may automatically free up space for backup of data newly added to or deleted from the primary data store, by selectively removing data from the deleted data store, based application of appropriate criteria.