In this article, we investigate the Variational Principle and develop thermodynamic formalism for correspondences. We define the measure-theoretic entropy for transition probability kernels and topological pressure for correspondences. Based on these two notions, we establish the following results: The Variational Principle holds and equilibrium states exist for continuous potential functions, provided that the correspondence satisfies some expansion property called forward expansiveness. If, in addition, the correspondence satisfies the specification property and the potential function is Bowen summable, then the equilibrium state is unique. On the other hand, for a distance-expanding, open, strongly transitive correspondence and a Hölder continuous potential function, there exists a unique equilibrium state, and the backward orbits are equidistributed. Furthermore, we investigate the Variational Principle for general correspondences. In complex dynamics, we establish the Variational Principle for the Lee-Lyubich-Markorov-Mukherjee anti-holomorphic correspondences, which are matings of some anti-ho\-lo\-mor\-phic rational maps with anti-Hecke groups and are not forward expansive. We also show a Ruelle-Perron-Frobenius theorem for a family of hyperbolic holomorphic correspondences of the form $\boldsymbol{f}_c (z)= z^{q/p}+c$.