Given that soil erosion is a primary cause of land degradation globally, it has been receiving increasing attention in food production regions, such as the Mollisol region in northeastern China. This study assessed soil quality under soil erosion degradation using a novel optimal data set (ODS) approach and a comparative minimum data set (MDS) approach based on soil quality indices (SQIs) within an agriculture watershed in Bin County, Heilongjiang Province, China. SQIs selection was contingent on multiple soil factors. Soil erosion rates was determined using cesium-137 technique. Relationships between soil quality and erosion or deposition rates were also analyzed. Results showed that erosion primarily drove soil redistribution, and soil quality grades were generally extremely low (approx. 80% of sampling sites), based on results from both the MDS and ODS approaches. However, soil quality varied significantly between erosion and deposition sites, it increased from upstream to midstream to downstream areas. Moreover, changes in SQIs and erosion rates exhibited spatially opposite trends, indicative of the impact that soil erosion has on soil quality, which was also confirmed by comparing representative soil properties at soil erosion and deposition sites. The good correlation between the MDS and ODS approaches indicated the feasibility of the ODS approach in estimating soil quality. Finally, the ODS approach is a cause-related method applying a relatively strict indicator selection procedure, which, compared to the MDS approach, could theoretically obtain more reliable results. Further studies are nevertheless necessary to assess the feasibility of this novel approach in other cases.