Discovering knowledge from huge databases with missing values is a challenging problem in Data Mining. In this paper, a novel hybrid algorithm for learning knowledge represented in Bayesian Networks is discussed. The new algorithm combines an evolutionary algorithm with the Expectation-Maximization (EM) algorithm to overcome the problem of getting stuck in sub-optimal solutions which occurs in most existing learning algorithms. The experimental results on the databases generated from several benchmark network structures illustrate that our system outperforms some state-of-the-art algorithms. We also apply our system to a direct marketing problem, and compare the performance of the discovered Bayesian networks with the response models obtained by other algorithms. In the comparison, the Bayesian networks learned by our system outperform others.