We study the formation and propagation of two-dimensional vortex solitons, i.e. solitons with a phase singularity, in optical materials with a nonlocal focusing nonlinearity. We show that nonlocality stabilizes the dynamics of an otherwise unstable vortex beam. This occurs for either single or higher charge fundamental vortices as well as higher order (multiple ring) vortex solitons. Our results pave the way for experimental observation of stable vortex rings in other nonlocal nonlinear systems including Bose-Einstein condensates with pronounced long-range interparticle interaction.