Cloud computing is becoming a key element in service provision on the Internet. Businesses are seizing the availability of infrastructure as service to obtain cost effective infrastructure solutions. However, in businesses the power of services emerges from the ability to combine different services in order to obtain some value added services. Cloud services composition presents some challenges like, service discovery and real time service evaluation; which are addressed in this paper by introducing a primal framework that enables dynamic specification of SLAs, in addition to SLA-based verification and composition of services on the Cloud. The verification is used as input to the composition and consists of verifying the functional and non-functional properties of the cloud service under test. An ongoing prototype implementation will evaluate the verification scheme and prove its importance in composing and selecting services on the cloud.