A streams manager monitors cost of one or more VMs hosting a streaming application, determines when cost can be reduced, and requests a cloud manager provision one or more VMs that have a lower cost. In response, the cloud manager provisions the VM(s) that have the lower cost. The streams manager then deploys a portion of the streaming application to the VM(s), thereby reducing the cost of running the streaming application.