Described is a system for rule-based re-tiering of backup data stored on a cloud-based object storage. More specifically, the system may re-tier objects based on one or more storage rules such that the system retains the ability to efficiently perform a full restore of backup data even when incremental backups are performed to a cloud-based object storage. To provide such a capability, the system may maintain a specialized metadata database that stores information indicating the backup time for each backup, and a list of objects required to perform a full restore to each of the backup times. Accordingly, when initiating a re-tiering based on one or more storage rules, the system may intelligently select candidate objects for re-tiering by leveraging the metadata database to ensure that objects that may still need to be referenced are not unnecessarily moved to a lower storage tier.