The nonlocal s-fractional minimal surface equation for Σ = ∂E where E is an open set in RN is given by HΣ s (p):= RN χE(x) − χEc(x) dx = 0 for all p ∈ Σ. |x − p|N+s Here 0 < s < 1, χ designates characteristic function, and the integral is understood in the principal value sense. The classical notion of minimal surface is recovered by letting s → 1. In this paper we exhibit the first concrete examples (beyond the plane) of nonlocal s−minimal surfaces. When s is close to 1, we first construct a connected embedded s-minimal surface of revolution in R3, the nonlocal catenoid, an analog of the standard catenoid |x3| = log(r+ r2 − 1). Rather than eventual logarithmic growth, this surface becomes asymptotic to the cone |x3| = r1 − s. We also find a two-sheet embedded s-minimal surface asymptotic to the same cone, an analog to the simple union of two parallel planes. On the other hand, for any 0 < s < 1, n, m ≥ 1, s−minimal Lawson cones |v|=α|u|, (u,v)∈Rn×Rm, are found to exist. In sharp contrast with the classical case, we prove their stability for small s and n+m=7, which suggests that unlike the classical theory (or the case s close to 1), the regularity of s-area minimizing surfaces may not hold true in dimension 7.