We consider the (unoriented) long-range percolation on ℤd in dimensions d≥1, where distinct sites x,y∈ℤd get connected with probability pxy∈[0,1]. Assuming pxy=|x−y|−s+o(1) as |x−y|→∞, where s>0 and |⋅| is a norm distance on ℤd, and supposing that the resulting random graph contains an infinite connected component C∞, we let D(x,y) be the graph distance between x and y measured on C∞. Our main result is that, for s∈(d,2d), D(x,y)=(log|x−y|)Δ+o(1), x,y∈C∞, |x−y|→∞, where Δ−1 is the binary logarithm of 2d/s and o(1) is a quantity tending to zero in probability as |x−y|→∞. Besides its interest for general percolation theory, this result sheds some light on a question that has recently surfaced in the context of “small-world” phenomena. As part of the proof we also establish tight bounds on the probability that the largest connected component in a finite box contains a positive fraction of all sites in the box.