We have developed a new approach (MDLEP) to learning Bayesian network structures based on the Minimum Description Length (MDL) principle and Evolutionary Programming (EP). It employs a MDL metric, which is founded on information theory, and integrates a knowledge-guided genetic operator for the optimization in the search process.