<p>We study the nonlocal Stefan problem, where the phase transition is described by a nonlocal diffusion as well as the change of enthalpy functions. By using a stochastic optimization approach introduced in Kim and Kim (The Stefan problem and free targets of optimal Brownian martingale transport, 2021. arXiv preprint <a href="http://arxiv.org/abs/2110.03831">arXiv:2110.03831</a>), we construct global-time weak solutions and give a probabilistic interpretation for the solutions. An important ingredient in our analysis is a probabilistic interpretation of the enthalpy and temperature variables in terms of a particle system. Our approach in particular establishes the connection between the parabolic obstacle problem and the Stefan problem for the nonlocal diffusions. For the melting problem, we show that our temperature-based solution coincides with the enthalpy-based ones studied in Athanasopoulos and Caffarelli (Adv Math 224(1):293–315, 2010), del Teso et al. (C R Math 355(11):1154–1160, 2017, Adv Math 305:78–143, 2017, Appl Sci 31(01):83–131, 2021), and obtain a new exponential convergence result.</p>