Many regions worldwide face soil loss rates that endanger future food supply. The installation of soil and water conservation measures reduces soil loss rates but comes with high labor costs. A multi-objective optimization allows considering both soil loss rates and labor costs, but required spatial data contains uncertainties. Yet, spatial data uncertainty has not been considered in research for allocating soil and water conservation measures. We aim to overcome that research gap by optimizing conservation measure allocations despite spatial data uncertainties. We propose a multi-objective genetic algorithm that creates optimal solutions that indicate which watersheds should be conserved. Stochastic objective values are computed from uncertain soil and precipitation variables to evaluate and compare solutions. The study is conducted in three rural areas in Ethiopia. The highest soil loss rate uncertainties result in objective values ranging up to 14%. The associated yield loss ranges with soil loss rates under uncertainties are comparable to reported yield loss risks from droughts. The uncertainty of labor requirement objective values is localised to less then 5% of the area in all three study areas. However, ranges in labor requirement estimations become up to 15 labor days per hectare in areas where labor requirements are uncertain. Upon further analysis of common characteristics and patterns in optimal solutions, we also conclude that the results can be used to define a temporal order for planning and implementing conservation measures.