We introduce a method to measure many-body magic in quantum systems based on a statistical exploration of Pauli strings via Markov chains. We demonstrate that sampling such Pauli–Markov chains gives ample flexibility in terms of partitions where to sample from: in particular, it enables to efficiently extract the magic contained in the correlations between widely-separated subsystems, which characterizes the nonlocality of magic. Our method can be implemented in a variety of situations. We describe an efficient sampling procedure using Tree Tensor Networks, that exploits their hierarchical structure leading to a modest $O(\log N)$ computational scaling with system size. To showcase the applicability and efficiency of our method, we demonstrate the importance of magic in many-body systems via the following discoveries: (a) for one dimensional systems, we show that long-range magic displays strong signatures of conformal quantum criticality (Ising, Potts, and Gaussian), overcoming the limitations of full state magic; (b) in two-dimensional $\mathbb{Z}_2$ lattice gauge theories, we provide conclusive evidence that magic is able to identify the confinement-deconfinement transition, and displays critical scaling behavior even at relatively modest volumes. Finally, we discuss an experimental implementation of the method, which only relies on measurements of Pauli observables.