In this paper we study the fundamental problem of finding small dense subgraphs in a given graph. For a real number s > 2, we prove that every graph on n vertices with average degree at least d contains a subgraph of average degree at least s on at most nd-s/s 2 (log d)Os(1) vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner.