Methods, systems, and computer program product embodiments for cataloging data in a backup storage environment, by a processor device, are provided. In a storage system using tape library data replication between an originating site and one or more backup sites, data catalog data is replicated between the originating site and the backup site such that replicated data moved from the originating site to the backup site is placed into a catalog duplicative of the originating site.