Continued access to sanitation and the improvements to public health that it provides requires safe fecal sludge management (FSM). Trained service providers offer the best path to achieve safe FSM in rural communities, but this service industry is hindered by a lack of understanding household valuation of FSM services in rural Cambodia. Using a discrete choice experiment, we characterize rural households’ preferences for four different FSM-service attributes across five provinces. We find that rural households prefer preventing contact with fecal sludge (FS) most among the tested FSM-service attributes, followed by reducing foul odor and producing fertilizer from FS. Reducing time to service delivery was also preferred comparably to producing fertilizer from FS when time to service delivery increased to 4 weeks. Preferences were also analyzed by province, poverty, and education, providing regional and demographic-specific results. Based on the study’s results, we recommend that Cambodia’s rural sanitation sector develop an FSM-service model that focuses on preventing human contact with FS. Premium levels of service that reduce foul odor and/or provide fertilizer from FS should be offered. Development practitioners should consider the strong preference heterogeneity for FSM-service attributes of households across and within provinces and demographics. These recommendations will provide practical benefits to FSM safety and ultimately improve public health.