Migrating an application from local compute resources to commercial cloud resources involves giving up full control of the physical infrastructure, as the cloud service provider (CSP) is responsible for managing the physical infrastructure, including its security. The reliance of a tenant on a CSP can create a trust issue around whether the CSP is upholding its end of the bargain. CSPs acknowledge this and provide a guarantee through a Service Level Agreement (SLA). SLAs need to be verified for satisfaction of the defined objectives. To avoid raising the trust issue again, such a verification procedure needs to be unbiased and independently achievable by both tenants and CSPs without one relying on the other party. In this paper, we consider an SLA offered by the provider that guarantees the integrity of tenants’ data, and propose to verify the SLA using an integrity checking method based on a distributed ledger. Our proposed method allows both CSPs and tenants to perform integrity checking without one party relying on the other. The method uses a blockchain as a distributed ledger to store evidence of data integrity. Assuming the ledger as a secure, trusted source of information, the evidence can be used to resolve conflicts between providers and tenants. In addition, we present a prototype implementation and an experimental evaluation to show the feasibility of our verification method and to measure the time overhead.