Multiagent planning has seen much progress with the development of formal models such as decentralized MDPs and POMDPs. However, the complexity of these models--NEXP-Complete even for two agents--has limited scalability. We identify certain mild conditions that are sufficient to make multiagent planning amenable to a scalable approximation w.r.t. the number of agents. This is achieved by constructing a graphical model in which likelihood maximization is equivalent to plan optimization. Inference processes in an Expectation-Maximization (EM) framework can be decomposed, often involving a small subset of agents and thereby facilitating scalability. We derive a global update rule using the EM algorithm that combines these local inferences to monotonically increase the overall solution quality. Experiments on a large multiagent planning benchmark confirm the benefits of the new approach in terms of runtime and scalability.