Summary: We propose a nonlocal continuum model to describe the size-dependent superelastic responses observed in recent experiments of shape memory alloys. The modeling approach extends a superelasticity formulation based on the martensitic volume fraction, and combines it with gradient plasticity theories. Size effects are incorporated through two internal length scales, an energetic length scale and a dissipative length scale, which correspond to the gradient terms in the free energy and the dissipation, respectively. We also propose a computational framework based on a variational formulation to solve the coupled governing equations resulting from the nonlocal superelastic model. Within this framework, a robust and scalable algorithm is implemented for large scale three-dimensional problems. A numerical study of the grain boundary constraint effect shows that the model is able to capture the size-dependent stress hysteresis and strain hardening during the loading and unloading cycles in polycrystalline SMAs.