Nonlocal spatial solitons are the optical spatial solitons in nonlocal nonlinear media. In this invited paper, a review is given about the progress on this subject. The nonlocal spatial solitons are phenomenologically modeled by the nonlocal nonlinear Schrodinger equation, which can be simplified to a linear model for a strong nonlocality. An exact analytical Gaussian-shaped solution to the linear model is obtained, and a spatial soliton called an accessible soliton is found to exist. A phase shift of such an accessible soliton can be very large comparable to its local counterpart, and this finding might be applied in integrated all-optical devices. More intriguing is the collision between two nonlocal spatial solitons. The interaction of two coherent accessible solitons is always attractive, independent of their relative phase, unlike in a local nonlinearity. Such an interaction behavior is experimentally observed in nematic liquid crystals, and a power-dependent X junction, AND, NOR, and XNOR gates are also experimentally demonstrated. This collisional characteristics has implications to all-optical switching and all-optical logic.