We prove that RANDOM EDGE, the simplex algorithm that always chooses a random improving edge to proceed on, can take a mildly exponential number of steps in the model of abstract objective functions (introduced by Wiliamson Hoke [27] and by Kalai [16] under different names). We define an abstract objective function on the n-dimensional cube for which the algorithm, started at a random vertex, needs at least exp(const ? n^1/3) steps with high probability. The best previous lower bound was quadratic. So in order for RANDOM EDGE to succeed in polynomial time, geometry must help.