The adoption of the cloud computing model continues to be dominated by startups seeking to build new applications that can take advantage of the cloud's pay-as-you-go pricing and resource elasticity. In contrast, large enterprises have been slow to adopt the cloud model, partly because migrating legacy applications to the cloud is technically non-trivial and economically prohibitive. Both challenges arise, in part, from the difficulty in discovering the complex dependencies that these legacy applications have on the underlying IT environment. In this paper, we introduce a novel Kullback-Leibler (KL) divergence based method that can systematically discover the complex server-to-server and application-to-server relationships. We evaluate our method using five real datasets from large enterprise migration efforts. Our results demonstrate that our new method is capable of finding critical application correlations; it performs better than traditional approaches, such as Bayesian or mutual information models. Additionally, by cleverly subdividing the sample space, we are able to uncover intriguing phenomena in different subspaces. These analyses aid migration engineers in a variety of tasks ranging from migration planning to failure mitigation, and can potentially lead to significant cost reduction in migration to cloud. © 2013 IFIP.