A new algorithm of extreme point tabu search that constructs globally optimal deci-sion trees for classification problem is presented in the paper. The algorithm can be used fornondifferentiable objective function. The method of global tree optimization for constructing de-cision tree with fixed structure is non -greedy. A multivariate decision tree can be represented as a set of disjunctive linear inequalities and the global tree optimization minmizesthe classification errors from the disjunctive linear inegualities.