Described is a system for intelligent re-tiering of backup data stored on a cloud-based object storage. More specifically, the system may re-tier objects 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 using a threshold time (e.g. expiry) to select object candidates for re-tiering, the system may leverage the metadata database to ensure that objects that may still need to be referenced are not unnecessarily moved to a lower storage tier.