Abstract: To solve the drawbacks of the random searching based algorithms for learning Bayesian networks,we introduced the Tabu search into Bayesian network structure learning problems,proposed a Tabu-search-based Bayesian network structure learning algorithm (TBN).First,the new algorithm generates the neighborhood solutions by add,subtract and reverse arc operators.And then,the Tabu list and aspiration criteria guide the search procedure corporately.After the iteration of the two steps above,the algorithm will finally obtain optimal or near optimal solutions.The experiment results on the benchmark data sets show that TBN has a simpler structure and faster speed.