Many regions worldwide face soil loss rates that endanger future food supply. Constructing soil and water conservation measures reduces soil loss but comes with high labor costs. Multi-objective optimization allows considering both soil loss rates and labor costs, however, required spatial data contain uncertainties. Spatial data uncertainty has not been considered for allocating soil and water conservation measures. We propose a multi-objective genetic algorithm with stochastic objective functions considering uncertain soil and precipitation variables to overcome this gap. We conducted the study in three rural areas in Ethiopia. Uncertain precipitation and soil properties propagate to uncertain soil loss rates with values that range up to 14%. Uncertain soil properties complicate the classification into stable or unstable soil, which affects estimating labor requirements. The obtained labor requirement estimates range up to 15 labor days per hectare. Upon further analysis of common patterns in optimal solutions, we conclude that the results can help determine optimal final and intermediate construction stages and that the modeling and the consideration of spatial data uncertainty play a crucial role in identifying optimal solutions.