The Erd\"os-R\'enyi random graph construction can be seen as inducing a probability measure concentrated on the Rado graph that is invariant under arbitrary permutations of the underlying set of vertices. It is natural to ask: Which other countable structures admit such invariant measures? In 2010, Petrov and Vershik provided the first instance of an invariant measure concentrated on Henson's countable homogeneous-universal triangle-free graph. We provide a characterisation of countable structures that admit invariant measures, in terms of the notion of (group-theoretic) definable closure. This leads to new examples and non-examples, including a complete list of countable homogeneous graphs, directed graphs, and partial orders that satisfy our criterion. Our proof uses infinitary logic to build on Petrov and Vershik's constructions, which involve sampling from certain continuum-sized objects. In the case when the measure is concentrated on a graph, these continuum-sized objects are in fact 'graph limits' in the sense of Lovasz and Szegedy (2006). Joint work with Nathanael Ackerman and Cameron Freer.