We demonstrate, experimentally and theoretically, surface-wave solitons occurring at the interface between a dielectric medium (air) and a nonlinear material with a very long-range nonlocal response. These surface solitons are always attracted toward the surface, and unlike their Kerr-like counterparts, they do not exhibit a power threshold.