Implementation of helminth control programs requires information on the distribution and prevalence of infection to target mass treatment to areas of greatest need. In the absence of data, the question of how many schools/communities should be surveyed depends on the spatial heterogeneity of infection and the cost efficiency of surveys. We used geostatistical techniques to quantify the spatial heterogeneity of soil-transmitted helminths in multiple settings in eastern Africa, and using the example of Kenya, conducted conditional simulation to explore the implications of alternative sampling strategies in identifying districts requiring mass treatment. Cost analysis is included in the simulations using data from actual field surveys and control programs. The analysis suggests that sampling four or five schools in each district provides a cost-efficient strategy in identifying districts requiring mass treatment, and that efficiency of sampling was relatively insensitive to the number of children sampled per school.