We introduce a methodology to estimate nonstabilizerness or “magic,” a key resource for quantum complexity, with neural quantum states (NQS). Our framework relies on two schemes based on Monte Carlo sampling to quantify nonstabilizerness via stabilizer Rényi entropy (SRE) in arbitrary variational wave functions. When combined with NQS, this approach is effective for systems with strong correlations and in dimensions larger than one, unlike tensor network methods. First, we study the magic content in an ensemble of random NQS, demonstrating that neural network parametrizations of the wave function capture finite nonstabilizerness besides large entanglement. Second, we investigate the nonstabilizerness in the ground state of the J1-J2 Heisenberg model. In one dimension, we find that the SRE vanishes at the Majumdar-Ghosh point J2 = J1/2, consistent with a stabilizer ground state. In two dimensions, a dip in the SRE is observed near maximum frustration around J2/J1 ≈ 0.6, suggesting a valence bond solid between the two antiferromagnetic phases.