We provide the first mathematical proof that the connective constant of the hexagonal lattice is equal to $\sqrt{2+\sqrt 2}$. This value has been derived non rigorously by B. Nienhuis in 1982, using Coulomb gas approach from theoretical physics. Our proof uses a parafermionic observable for the self avoiding walk, which satisfies a half of the discrete Cauchy-Riemann relations. Establishing the other half of the relations (which conjecturally holds in the scaling limit) would also imply convergence of the self-avoiding walk to SLE(8/3).