We present a recurrence-transience classification for discrete-time Markov chains on manifolds with negative curvature. Our classification depends only on geometric quantities associated to the increments of the chain, defined via the Riemannian exponential map. We deduce that there exist Markov chains on a large class of such manifolds which are both recurrent and have zero average drift at every point. We give an explicit example of such a chain on hyperbolic space of arbitrary dimension, and also on a stochastically incomplete manifold. We also prove that such recurrent chains cannot be uniformly elliptic, in contrast with the Euclidean case.