We consider the cloud workload placement problem, which is a mapping of logical to physical entities, that satisfies some constraints and optimizes an objective function. We describe an efficient solution technique that is based on random search methods and uses biased statistical sampling methods. In particular, the proposed technique utilizes (1) importance sampling as a mechanism for characterizing the optimal solution through marginal distributions, (2) independent sampling via a modified Gibbs sampler with intra-sample dependency, and (3) a jumping distribution that uses conditionals derived from the relationship constraints given in the user request and cloud system topology, and the importance sampling marginal distributions as posterior distributions. We demonstrate the feasibility of our methodology using several large-size simulation experiments. In a case where an optimal solution may be obtained, we show that our method is within 20% of optimality. Since the magnitude of biasing impacts the quality of placement, we investigate the tradeoff between biasing and optimality of placement solutions.