Example methods and apparatus asynchronously verify data stored in a cloud data storage system. One embodiment comprises a monitoring circuit that determines if a data auditing condition associated with a cloud storage system or archived data stored in the cloud storage system has been met, a metadata mirror circuit that controls a metadata mirror to provide metadata, including a first checksum, associated with the archived data to the apparatus, a checksum circuit that computes a second checksum based on the archived data, a verification circuit that generates an audit of the first checksum and the second checksum by comparing the second checksum with the first checksum, and a reporting circuit that generates a log of the audit, that provides the log to the data storage system, and that provides a notification of a data integrity failure to a user associated with the archived data.