Abstract: Learning structure from incomplete data is one of the difficulties of learning Bayesian networks because of computational complexity. In this paper, an evolutionary algorithm combined with expectation is proposed. Fitness function is presented, which based on expectation, converts incomplete data to complete data utilizing current best structure of evolutionary process to reduce computational complexity, ensuring that this algorithm can evolve for good structure. Besides, encoding is given, and genetic operators are designed, which provides guarantee of convergence. Experimental results show that this algorithm can effectively learn Bayesian network structure from incomplete data.