The Naive Bayesian classifier provides a very simple and effective model for machine learning, but its attribute independence assumption is often violated in the real world. To improve the performance of Bayesian classifier, we present a novel algorithm called Evolutional One-dependence Augmented Naive Bayes(EANB), which selects the attributes? parents by carrying an evolutional search through the whole space of attributes. Experimentally testing on the whole 36 UCI datasets recommended by Weka [1], we compare our algorithm to NB, SBC [2], TAN [3] and C4.5[4]. The result shows that our algorithm outperforms NB, SBC and TAN significantly, and outperforms C4.5 slightly in term of classification accuracy.