Simulated annealing is a numerical algorithm that can be used to impose statistical structures on numerical grids representing heterogeneous rock or sediment. In this paper, we use the flexibility of simulated annealing to generate grids with Markov statistical structures. Our purpose is to transmit the rich geological information captured in Markov statistics into stochastic grids while maintaining the flexibility of annealing to honor field data. Performance issues that compromise annealing grids imbued with Markovian properties include scales of bedding or rock bodies relative to grid size, and the amount of geological complexity in the embedded Markov structures. The remedies to these issues include proper selection of grid size, careful choice of annealing type, and consideration of an alternative annealing stopping rule based on a chi-squared test statistic. If performance issues are overcome, complex stratal patterns such as higher-order dependency, cyclicity, and directionality can be replicated in grids by this method. In addition, accounting for variations in depositional rate allows for transference of Markov structures obtained from vertical boreholes to the horizontal dimension when other information is lacking. A field example using borehole data collected at the Gloucester special waste site near Ottawa, Canada, as well as synthetic examples, demonstrate the technique and performance issues.