- What if Nature allowed nonlocal correlations other than predicted by quantum mechanics -- would that be in conflict with some physical principle? Various principles have been put forward in the past two decades in an attempt to single out quantum nonlocality. However, none of them can explain the set of quantum correlations arising in the simplest bipartite scenario. Here it is shown that in inherently indeterministic theories a specific notion of locality gives rise to both familiar and new characterizations of quantum correlations. In particular, we identify a condition which states that in an indeterministic theory the uncertainty relations witnessed by an experimenter are local in the sense that they cannot be influenced by the other experimenters' choices of measuring instruments. Without assuming quantum mechanics, it is shown that this condition induces a particular statistical structure that gives rise to known bounds on bipartite, binary quantum correlations, as well as novel bounds on the correlations in general multipartite scenarios. Our results show that theories with correlations other than quantum do not satisfy this notion of locality and are therefore either incompatible with indeterminism (in the sense of this work) or allow experimenters to nonlocally temper with the uncertainty relations of their peers.