Techniques for handling fragmentation of archived data in cloud/object storage are provided. In one set of embodiments, a computer system can upload a new snapshot of a data set to the cloud/object storage, where the new snapshot comprises a plurality of data blocks, and where the new snapshot is uploaded as one or more data objects and one or more metadata objects. For each data block in the plurality of data blocks, the computer system can identify an existing data object in the cloud/object storage where the data block is currently stored. The computer system can further select, from among the identified existing data objects, a subset of the existing data objects that are part of a snapshot created in the cloud/object storage at least a predefined number of snapshots before the new snapshot, and select one or more data blocks of one or more data objects in the subset that have not be overwritten by another snapshot. The computer system can then upload the one or more data blocks as part of the new snapshot.