A multitude of issues affect the broader adoption of Cloud computing, with the perceived lack of trust on the Cloud Service Providers (CSPs) often listed as a significant concern. To address this, CSPs typically set up Service Level Agreements (SLAs) that contractually list what the CSP is obligated to provide to meet the customer requirements. While SLAs are promising as a concept, the inadequacy of schemes to actually monitor and validate the run-time compliance of SLAs limits the customer's capability to evaluate the offered services to assess the actual trust to put in the CSPs. In this paper, we propose a methodology to validate SLAs and detect service violations over the life of the service. The SLA consists of a list of service attributes that are required by the customer and committed by the CSP. In order to validate an SLA, we evaluate each SLA attribute either qualitatively or quantitatively as relevant. The evaluation provides reproducible assurance to a customer for trusting the CSP based on its fulfillment of the customer's requirements. We classify requirement violations into 'trust states' according to the customer defined preferences and the CSP can be in varied trust states depending on the severity level of the violations. We demonstrate assessing the trust state of a CSP based on the services involved in launching and migrating a virtual machine in Infrastructure-as-a-Service (IaaS) offering. © 2016 IEEE.