The calculation of Hartree-Fock exchange (HFX) is computationally demanding for large systems described with high-quality basis sets. In this work, we show that excellent performance and good accuracy can nevertheless be obtained if an auxiliary density matrix is employed for the HFX calculation. Several schemes to derive an auxiliary density matrix from a high-quality density matrix are discussed. Key to the accuracy of the auxiliary density matrix methods (ADMM) is the use of a correction based on standard generalized gradient approximations for HFX. ADMM integrates seamlessly in existing HFX codes and, in particular, can be employed in linear scaling implementations. Demonstrating the performance of the method, the effect of HFX on the structure of liquid water is investigated in detail using Born?Oppenheimer molecular dynamics simulations (300 ps) of a system of 64 molecules. Representative for large systems are calculations on a solvated protein (Rubredoxin), for which ADMM outperforms the corresponding standard HFX implementation by approximately a factor 20.