Abstract Efficient designs for nested sampling are needed in many areas of science. In the geosciences they are used to discover the important spatial scales on which properties vary. However, while the practical advantages and disadvantages of various nested designs have been discussed, no attempt has been made to optimize nested sampling schemes. This paper shows how an optimal nested sampling design can be found by a method of numerical combinatorial optimization: simulated annealing. The sample design is optimized over a space of possible designs for a fixed sample size and predetermined levels (spatial scales). The objective function for optimization is based on the expected covariance matrix for errors in the estimates of variance components, and so depends on what those components are. By simulation it was shown that optimized sampling schemes can detect scale-dependent variance components with common requirements for statistical power on smaller total sample sizes than are required with commonly used spatially nested sample designs such as the balanced design. Although the optimized design depends on the underlying covariance structure, sampling designs can be identified that perform better than the commonly used ones over a wide range of conditions.