Bayesian networks have a wide array of applications with its ability to model causal relationships in any given system. Given the immense complexity and size of real problems, it is impossible to manually construct Bayesian networks. The automatic learning of Bayesian networks from data is hence an important task. However, in most industrial applications, the number of variables involved in any given system is large. Existing algorithms need an impractical amount of time to learn such networks due to poor scalability with dimensionality. In this paper, a constraint-based algorithm, named MICHO, is introduced to overcome this barrier. MICHO synergistically integrates an information-theory-based approach and an independence-based approach to efficiently learn a Bayesian Network. Using Mutual Information (MI), basic Bayesian network and graph concepts to reduce the search space, a preliminary base graph can be quickly generated. Refinements are then carried out using a minimal number of higher order tests involving minimum cardinality d-separating sets to obtain the final Bayesian network structure. Experiments involving real, large and high-dimensional datasets show that MICHO can perform up to 25 times faster than K2 while achieving similar accuracy.