CRISPR-Cas immune systems utilize RNA-guided nucleases to protect bacteria from bacteriophage infection. Bacteriophages have in turn evolved inhibitory "anti-CRISPR" (Acr) proteins, including six inhibitors (AcrIIA1-AcrIIA6) that can block DNA cutting and genome editing by type II-A CRISPR-Cas9 enzymes. We show here that AcrIIA2 and its more potent homolog, AcrIIA2b, prevent Cas9 binding to DNA by occluding protein residues required for DNA binding. Cryo-EM-determined structures of AcrIIA2 or AcrIIA2b bound to S. pyogenes Cas9 reveal a mode of competitive inhibition of DNA binding that is distinct from other known Acrs. Differences in the temperature dependence of Cas9 inhibition by AcrIIA2 and AcrIIA2b arise from differences in both inhibitor structure and the local inhibitor-binding environment on Cas9. These findings expand the natural toolbox for regulating CRISPR-Cas9 genome editing temporally, spatially, and conditionally.