  We develop a rigorous theory of non-local Poisson structures, built on the
notion of a non-local Poisson vertex algebra. As an application, we find
conditions that guarantee applicability of the Lenard-Magri scheme of
integrability to a pair of compatible non-local Poisson structures. We apply
this scheme to several such pairs, proving thereby integrability of various
evolution equations, as well as hyperbolic equations.
