Place and grid cells, found in the hippocampus (HPC) and medial entorhinal cortex (mEC) respectively, fire at specific locations across physical space. Whereas place cells are thought to be driven predominantly be environmental sensory inputs, grid cells have been shown to be also partially driven by self-motion. We propose that place and grid cells may interact to perform probabilistic structural learning. We compare the predictions of our model to several experimentally observed phenomena and argue that approximate inference may be computed by local message passing in the HPC-mEC system.