Fuzzy K-Modes is an effective method for clustering categorical data. This method is as extensions of fuzzy k-means algorithm by using modes in the process of matching the dissimilarity measure to update centroid of the cluster and to obtain the optimal solution. Nevertheless, Fuzzy K-Modes has the disadvantage of the possibility of stopping in the optimal local solution. Artificial Bee Colony (ABC) is an optimization method that has been proven effective and has the ability to obtain global solutions. This study proposes a hybridization between the Artificial Bee Colony algorithm and Fuzzy K-Modes for clustering categorical data. The implementation of hybridization between Artifical Bee Colony and Fuzzy K-Modes (ABC-FKMO) has been proven to be able to improve the performance of categorical data clustering especially in the aspects of Objective Function, F-Measure, and Accuracy. The test results with datasets of the Soybean Disease, Breast Cancer and Congressional Voting Records from the UCI data repository, showed the Accuracy averages of 0.991, 0.615, and 0.867. Objective Function is better at an average of 2.73%, F-Measure is better at an average of 4.31% and Accuracy is better at an average of 5.16%.