Service composition provides value-adding services through composing basic Web services, which may be provided by various organizations. Cloud computing presents an efficient managerial, on-demand, and scalable way to integrate computational resources (hardware, platform, and software). However, existing Cloud architecture lacks the layer of middleware to enable dynamic service composition. To enable and accelerate on-demand service composition, the authors explore the paradigm of dynamic service composition in the Cloud for Pervasive Service Computing environments and propose a Cloud-based Middleware for Dynamic Service Composition (CM4SC). In this approach, the authors introduce the CM4SC ‘Composition as a Service’ middleware layer into conventional Cloud architecture to allow automatic composition planning, service discovery and service composition. The authors implement the CM4SC middleware prototype utilizing Windows Azure Cloud platform. The prototype demonstrates the feasibility of CM4SC for accelerating dynamic service composition and that the CM4SC middleware-accelerated Cloud architecture offers a novel way for realizing dynamic service composition.