Associative classification (AC) is a data mining approach that combines classification and association rule mining to build classification models (classifiers). Experimental results show that in average the CBA-based approaches could achieve higher accuracy than some of the traditional classification methods. In this paper, we focus on associative classification, where class association rules are generated and analyzed to build a simple, compact, understandable and relatively accurate classifier. Furthermore, we discuss how overall coverage and average rule coverage of such classifiers affect their classification accuracy. We compare our method that uses constrained exhaustive search with some “classical” classification rule learning algorithm that uses greedy heuristic search on accuracy in some “real-life” datasets. We have performed experiments on 11 datasets from UCI Machine Learning Database Repository. Experimental evaluation shows that with decreasing overall coverage our proposed method tends to get slightly worse classification accuracy than the “classical” classification rule learning algorithms. Otherwise, the accuracy is similar or on some datasets even better than Naive Bayes and C4.5. On the other hand, the average rule coverage of our proposed method seems to have no effect on classification accuracy.