We cannot see others’ mental states, so we infer them by watching how people behave. Bayesian inference in a model of rational action – called inverse planning – captures how humans infer desires from observable actions. These models represent desires as simple associations between agents and world states. In this paper we show that by representing desires as probabilistic programs, an inverse planning model can infer complex desires underlying complex behaviors—desires with temporal and logical structure, which can be fulfilled in different ways. Our model, which combines basic desires via logical primitives, is inspired by recent probabilistic grammar-based models of concept learning. Through an experiment where we vary behaviors parametrically, we show that our model predicts with high accuracy how people infer complex desires. Our work sheds light on the representations underlying mental states, and paves the way towards algorithms that can reason about others’ minds as we do.