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 for the local case, 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 solution coincides with those studied in the literature, and obtain a new exponential convergence result.