  This paper introduces a new notion of a Fenchel conjugate, which generalizes
the classical Fenchel conjugation to functions defined on Riemannian manifolds.
We investigate its properties, e.g.,~the Fenchel--Young inequality and the
characterization of the convex subdifferential using the analogue of the
Fenchel--Moreau Theorem. These properties of the Fenchel conjugate are employed
to derive a Riemannian primal-dual optimization algorithm, and to prove its
convergence for the case of Hadamard manifolds under appropriate assumptions.
Numerical results illustrate the performance of the algorithm, which competes
with the recently derived Douglas--Rachford algorithm on manifolds of
nonpositive curvature. Furthermore, we show numerically that our novel
algorithm even converges on manifolds of positive curvature.
