Objectives: Missing data is commonplace in clinical databases, which are being increasingly used for research. Without giving any regard to missing data, results from analysis may become biased and unrepresentative. Clinical databases contain mainly categorical variables. This study aims to assess the methods used for imputation in categorical variables. Materials and methods: We utilized data extracted from paper-based maternal health records from Kawempe National Referral Hospital, Uganda. We compared the following imputation methods for categorical data in an empirical analysis: Mode, K-Nearest Neighbors (KNN), Random Forest (RF), Sequential Hot-Deck (SHD), and Multiple Imputation by Chained Equations (MICE). The five imputation methods were first compared by accuracy of predicting the missing values. Next, the imputation methods were compared by predictive accuracy of the outcome variable in four classifiers. The consistency of performance of imputation methods across different levels of missing data (5%–50 %) was assessed by Kendall's W test. Results: KNN imputation had the highest precision score at levels (5%–50 %) of MCAR missing data. At lower proportions of missing data (5 %, 10 %, 15 %, 20 %), RF imputation had the second-highest precision score. SHD imputation had the worst precision at all levels of missing data. In the prediction of the outcome, the methods performed differently at all proportions of missing data in the four classifiers. Even though KNN imputation was the best method in predicting the missing values, it did not consistently enhance the predictive accuracy of the classifiers at all levels of missing data. Our findings show that a high precision score of an imputation method does not translate into higher predictive accuracy in classifiers. Conclusions: KNN imputation is the best method in predicting missing values in categorical variables. There is no universal best imputation method that yields the highest predictive accuracy at all proportions of missing data.