Soil degradation is a critical global challenge, and its accurate assessment is fundamental to advancing sustainable soil management and ensuring food security. The minimum dataset (MDS) has been widely adopted in soil degradation assessments, typically constructed using various statistical and machine learning techniques. However, a lack of systematic comparisons among these methods introduces substantial uncertainty into degradation evaluations. Here, we propose a two-step approach to optimize MDS construction using 99 dryland red soil samples from Ji'an, China, and the analysis of 30 physical, chemical, and biological indicators. First, machine learning algorithms-including Decision Tree, Random Forest, Gradient Boosting Regression Tree (GBRT), and Extreme Gradient Boosting-were employed for feature selection. Subsequently, indicator weighting and scoring functions were applied to assess the degree of soil degradation. Our results demonstrate that the proposed two-step approach outperforms both conventional statistical dimensionality reduction techniques (i.e., principal component and K-means cluster analyses) and the direct application of machine learning models. Multiple model evaluation metrics-including the coefficient of determination, error metrics, statistical tests, and correlation with crop yield-consistently indicate that the MDS derived from the GBRT-based two-step approach is highly suitable for rapid characterization of dryland red soil degradation. This MDS comprises organic carbon, microaggregates, bulk density, field capacity, urease, nitrate nitrogen, available phosphorus, available potassium, and total phosphorus. The assessment further revealed that dryland soils in the study area were generally at a moderate degradation level, primarily driven by the combined effects of climatic, soil, topographic, and anthropogenic factors. This study validates the two-step approach as an effective tool for assessing dryland red soil degradation and offers new insights for the development of a global soil degradation monitoring system.