We propose Neural Walk-on-Spheres (NWoS), a novel neural PDE solver for the efficient solution of high-dimensional Poisson equations. Leveraging stochastic representations and Walk-on-Spheres methods, we develop novel losses for neural networks based on the recursive solution of Poisson equations on spheres inside the domain. The resulting method is highly parallelizable, does not require spatial gradients for the loss, and naturally includes boundary conditions without balancing penalty terms. We provide a comprehensive comparison against competing methods based on PINNs, the Deep Ritz method, and (backward) stochastic differential equations. In several challenging, high-dimensional numerical examples, we demonstrate the superiority of NWoS in terms of accuracy, speed, and computational costs. Compared to commonly used PINNs, this can result in more than 750 times reduced memory usage or 10 times better performance. Furthermore, we apply NWoS to problems in the context of PDE-constrained optimization as well as molecular dynamics to show its efficiency in practical applications.