In the Densest k -Subgraph problem, given an undirected graph G and an integer k , the goal is to find a subgraph of G on k vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves only O ( n 1 4+ ) approximation ratio (Bhaskara et al., 2010), previous attempts at proving hardness of approximation, including those under average case assumptions, fail to achieve a polynomial ratio; the best ratios ruled out under any worst case assumption and any average case assumption are only any constant (Raghavendra and Steurer, 2010) and 2 ( log 2 3 n ) (Alon et al., 2011) respectively. In this work, we show, assuming the exponential time hypothesis (ETH), that there is no polynomial-time algorithm that approximates Densest k -Subgraph to within n 1 ( log log n ) c factor of the optimum, where 0"> c 0 is a universal constant independent of n . In addition, our result has "perfect completeness", meaning that we prove that it is ETH-hard to even distinguish between the case in which G contains a k -clique and the case in which every induced k -subgraph of G has density at most 1 n − 1 ( log log n ) c in polynomial time. Moreover, if we make a stronger assumption that there is some constant 0"> 0 such that no subexponential-time algorithm can distinguish between a satisfiable 3SAT formula and one which is only (1 − ) -satisfiable (also known as Gap-ETH), then the ratio above can be improved to n f ( n ) for any function f whose limit is zero as n goes to infinity (i.e. f o (1) ).