This research addresses the challenge of declining soil fertility in Pamekasan, East Java, by proposing a machine learning approach to improve the accuracy of soil fertility classification and provide data-driven recommendations. Conventional methods like linear regression and expert systems are limited in capturing the complexity of soil variables, leading to less accurate results. Therefore, this study compares the performance of two machine learning algorithms, Random Forest and XGBoost, in classifying soil fertility levels based on nutrient content (N, P, K, and micronutrients) and soil pH. The dataset, consisting of 880 soil samples from Pamekasan, revealed an imbalance, with the high-fertility class accounting for only 39 samples. After data preprocessing, both models were evaluated. The Random Forest model achieved an overall accuracy of 90.34%, slightly outperforming XGBoost, which reached 88.64%. Random Forest demonstrated superior performance in detecting low-fertility land (recall 0.97) and medium-fertility land (precision 0.93, recall 0.88). For the high-fertility minority class, Random Forest showed better recall (0.60) than XGBoost (0.40), while maintaining perfect precision (1.00). The study concludes that Random Forest is the optimal model for classifying soil fertility in Pamekasan. These findings provide a basis for more precise, efficient, and sustainable fertilization recommendations, which are expected to help farmers optimize productivity and support the sustainability of the local agricultural ecosystem by reducing excessive fertilizer use.