Much research in the social sciences is based on territorial units such as states, but not much is known about the causes of the observed partitioning of space into these units. Arguing that an important reason for this state of affairs is methodological, we here introduce a statistical model that can be used to analyze the determinants of partitionings of space into non-overlapping and contiguous units. Our Probabilistic Spatial Partition Model (PSPM) allows for a flexible discretization of space, accounts for structural and spatial dependencies, and generates meaningful predictions. These qualities are achieved by understanding spatial partitionings as a clustering of vertices in a spatial network in which edge characteristics affect the probability of two vertices sharing membership in a partition. We model this process as a Conditional Random Field, use a Pseudo Maximum Likelihood estimator to estimate its parameters, and propose a parametric bootstrap to derive valid uncertainty estimates. A series of Monte Carlo experiments shows that the method produces consistent estimates in most regions of the parameter space. Our illustrative application explores the natural and social predictors of the partitioning of Europe into states.