Ant Colony Optimization (ACO) algorithm has been applied to data mining recently. Aiming at Ant Miner, a classification rule learning algorithm based on ACO, this paper presents an enhanced Ant Miner, which includes two main contributions. Firstly, a rule punishing operator is employed to reduce the number of rules and the number of conditions. Secondly, an adaptive state transition rule and a mutation operator are applied to the algorithm to speed up the convergence rate. The results of experiments on some data sets demonstrate that the Enhanced Ant-Miner can quickly discover better classification rules which have roughly competitive predicative accuracy and short rules.