The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be (2−εd)nln(d)/d≤α(G(n,m))≤(2+εd)nln(d)/d with high probability, with εd→0 in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size nln(d)/d, i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size (1+ε)nln(d)/d for any fixed ε>0 (independent of both d and n). In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point k∼nln(d)/d. Roughly speaking, we prove that independent sets of size k>(1+ε)nln(d)/d form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015