There is a significant portion of the South African population with unknown HIV status, which slows down epidemic control despite the progress made in HIV testing. Machine learning (ML) has been effective in identifying individuals at higher risk of HIV infection, for whom testing is strongly recommended. However, there are insufficient predictive models to inform targeted HIV testing interventions in South Africa. By harnessing the power of supervised ML (SML) algorithms, this study aimed to identify the most consistent predictors of HIV testing in repeated adult population-based surveys in South Africa. The study employed four SML algorithms, namely, decision trees, random forest, support vector machines (SVM), and logistic regression, across the five cross-sectional cycles of the South African National HIV Prevalence, Incidence, and Behavior and Communication Survey (SABSSM) datasets. The Human Science Research Council (HSRC) conducted the SABSSM surveys and made the datasets available for this study. Each dataset was split into 80% training and 20% testing sets with a 5-fold cross-validation technique. The random forest outperformed the other models across all five datasets with the highest accuracy (80.98%), precision (81.51%), F-score (80.30%), area under the curve (AUC) (88.31%), and cross-validation average (79.10%) in the 2002 data. Random forest achieved the highest classification performance across all the dates, especially in the 2017 survey. SVM had a high recall (89.12% in 2005, 86.28% in 2008) but lower precision, leading to a suboptimal F-score in the initial analysis. We applied a soft margin to the SVM to improve its classification robustness and generalization, but the accuracy and precision were still low in most surveys, increasing the chances of misclassifying individuals who tested for HIV. Logistic regression performed well in terms of accuracy = 72.75, precision = 73.64, and AUC = 81.41 in 2002, and the F-score = 73.83 in 2017, but its performance was somewhat lower than that of the random forest. Decision trees demonstrated moderate accuracy (73.80% in 2002) but were prone to overfitting. The topmost consistent predictors of HIV testing are knowledge of HIV testing sites, being a female, being a younger adult, having high socioeconomic status, and being well-informed about HIV through digital platforms. Random forest's ability to analyze complex datasets makes it a valuable tool for informing data-driven policy initiatives, such as raising awareness, engaging the media, improving employment outcomes, enhancing accessibility, and targeting high-risk individuals. By addressing the identified gaps in the existing healthcare framework, South Africa can enhance the efficacy of HIV testing and progress towards achieving the UNAIDS 2030 goal of eradicating AIDS.