We study the existence and properties of solutions and free boundaries of the one-phase Stefan problem with fractional diffusion posed in Double-struck capital R-N. In terms of the enthalpy h(x,t), the evolution equation reads partial differential th + (-Delta)(s)phi(h) = 0, while the temperature is defined as u := phi(h) :=max{h - L, 0} for some constant L > 0 called the latent heat, and (-Delta)s stands for the fractional Laplacian with exponent s is an element of (0, 1). We prove the existence of a continuous and bounded selfsimilar solution of the form h(x,t) = H(xt-(1/(2s))) which exhibits a free boundary at the change-of-phase level h(x,t) = L. This level is located at the line (called the free boundary) x(t) = xi 0t(1/(2s)) for some xi 0 > 0. The construction is done in 1D, and its extension to N-dimensional space is shown. We also provide well-posedness and basic properties of very weak solutions for general bounded data h0 in several dimensions. The temperatures u of these solutions are continuous functions that have finite speed of propagation, with possible free boundaries. We obtain estimates on the growth in time of the support of u for solutions with compactly supported initial temperatures. Besides, we show the property of conservation of positivity for u so that the support never recedes. On the contrary, the enthalpy h has infinite speed of propagation and we obtain precise estimates on the tail. The limits L -> 0+, L -> +infinity, s -> 0+ and s -> 1- are also explored, and we find interesting connections with well-studied diffusion problems. Finally, we propose convergent monotone finite-difference schemes and include numerical experiments aimed at illustrating some of the obtained theoretical results, as well as other interesting phenomena.