This paper presents the formulation and numerical implementation of a self-consistent treatment of orbital-dependent exchange-correlation functionals within the Projector Augmented Wave (PAW) method of Blöchl [Phys. Rev. B 50 17953 (1994)] for electronic structure calculations. The methodology is illustrated with binding energy curves for C in the diamond structure and LiF in the rock salt structure, comparing results from the Hartree-Fock (HF) formalism and the Optimized Effective Potential (OEP) formalism in the so-called KLI approximation [Krieger, Li, and Iafrate, Phys. Rev. A 45, 101 (1992)] with those of the local density approximation (LDA). While the work here uses pure Fock exchange only, the formalism can be applied to orbital-dependent functionals more generally.