In this paper, we propose a new method for constructing decision trees based on Ant Colony Optimization (ACO). The ACO is a metaheuristic inspired by the behavior of real ants, where they search for optimal solutions by considering both local heuristic and previous knowledge, observed by pheromone changes. Good results of the ant colony algorithms for solving combinatorial optimization problems suggest an appropriate effectiveness of the approach also in the task of constructing decision trees. In order to improve the accuracy of decision trees we propose an Ant Colony algorithm for constructing Decision Trees (ACDT - www.ACDTalgorithm.com). A heuristic function used in the new algorithm is based on the splitting rule of the CART algorithm (Classification and Regression Trees). The proposed algorithm is evaluated in terms of exploration/exploitation rate, heuristic function, cooperation among ants, initial pheromone value.