Despite the utility of CRISPR-Cas9 nucleases for genome editing, the potential for off-target activity limits their application, especially for therapeutic purposes. We developed a yeast-based assay to identify optimized Streptococcus pyogenes Cas9 (SpCas9) variants that enables simultaneous evaluation of on- and off-target activity. We screened a library of SpCas9 variants carrying random mutations in the REC3 domain and identified mutations that increased editing accuracy while maintaining editing efficiency. We combined four beneficial mutations to generate evoCas9, a variant that has fidelity exceeding both wild-type (79-fold improvement) and rationally designed Cas9 variants (fourfold average improvement), while maintaining near wild-type on-target editing efficiency (90% median residual activity). Evaluating evoCas9 on endogenous genomic loci, we demonstrated a substantially improved specificity and observed no off-target sites for four of the eight single guide RNAs (sgRNAs) tested. Finally, we showed that following long-term expression (40 d), evoCas9 strongly limited the nonspecific cleavage of a difficult-to-discriminate off-target site and fully abrogated the cleavage of two additional off-target sites.