We derive an eikonal approximation to high energy interactions in Anti-de Sitter spacetime, by generalizing a position space derivation of the eikonal amplitude in flat space. We are able to resum, in terms of a generalized phase shift, ladder and cross ladder graphs associated to the exchange of a spin j field, to all orders in the coupling constant. Using the AdS/CFT correspondence, the resulting amplitude determines the behavior of the dual conformal field theory four-point function < O1O2O1O2 > for small values of the cross ratios, in a Lorentzian regime. Finally we show that the phase shift is dominated by graviton exchange and computes, in the dual CFT, the anomalous dimension of the double trace primary operators O-1 partial derivative...partial derivative O-2 of large dimension and spin, corresponding to the relative motion of the two interacting particles. The results are valid at strong t'Hooft coupling and are exact in the 1/N expansion.