We introduce a formal model for deployment and hosting of a dynamic grid service wherein the service provider must pay a resource provider for the use of computational resources. Our model produces policies that balance the number of required resources with the desire to keep the cost of hosting the service to a minimum. The two components of cost that we consider are the deployment cost and the cost to keep the service active, which we view as a lease. We cast the problem in a dynamic programming framework and we are able to show that the model makes good leasing decisions in the face of such uncertainties as random demand for the service and random execution times of service requests. The results show that the policies obtained from the model reduce the cost of hosting a service and significantly reduce the variance of that cost.