Background: Melioidosis is a frequently fatal infectious disease caused by the soil dwelling Gram-negative bacterium Burkholderia pseudomallei. Environmental sampling is important to identify geographical distribution of the organism and related risk of infection to humans and livestock. The aim of this study was to evaluate spatial distribution of B. pseudomallei in soil and consider the implications of this for soil sampling strategies. Methods and Findings: A fixed-interval sampling strategy was used as the basis for detection and quantitation by culture of B. pseudomallei in soil in two environmental sites (disused land covered with low-lying scrub and rice field) in northeast Thailand. Semivariogram and indicator semivariogram were used to evaluate the distribution of B. pseudomallei and its relationship with range between sampling points. B. pseudomallei was present on culture of 80/100 sampling points taken from the disused land and 28/100 sampling points from the rice field. The median B. pseudomallei cfu/gram from positive sampling points was 378 and 700 for the disused land and the rice field, respectively (p = 0.17). Spatial autocorrelation of B. pseudomallei was present, in that samples taken from areas adjacent to sampling points that were culture positive (negative) for B. pseudomallei were also likely to be culture positive (negative), and samples taken from areas adjacent to sampling points with a high (low) B. pseudomallei count were also likely to yield a high (low) count. Ranges of spatial autocorrelation in quantitative B. pseudomallei count were 11.4 meters in the disused land and 7.6 meters in the rice field. Conclusions: We discuss the implications of the uneven distribution of B. pseudomallei in soil for future environmental studies, and describe a range of established geostatistical sampling approaches that would be suitable for the study of B. pseudomallei that take account of our findings.