Abstract Recent progress on external-memory MDP solvers, in particular PEMVI [Dai et al., 2008], has enabled optimal solutions to large probabilistic planning problems. However, PEMVI requires a human to manually partition the MDP before the planning algorithm can be applied — putting an added burden on the domain designer and detracting from the vision of automated planning. This paper presents a novel partitioning scheme, which automatically subdivides the state space into blocks that respect the memory constraints. Our algorithm fifirst applies static domain analysis to identify candidates for partitioning, and then uses heuristic search to generate a ‘good’ partition. We evaluate the usefulness of our method in the context of PEMVI across many benchmark domains, showing that it can successfully solve extremely large problems in each domain. We also compare the performance of automatic partitioning with previously reported results using human-designed partitions. Experiments show that our algorithm generates signififi- cantly superior partitions, which speed MDP solving and also yield vast memory savings