Zinc finger nucleases (ZFNs) are powerful tools for gene therapy and genetic engineering. The high specificity and affinity of these chimeric enzymes are based on custom-designed zinc finger proteins (ZFPs). To improve the performance of existing ZFN technology, we developed an in vivo evolution-based approach to improve the efficacy of the FokI cleavage domain (FCD). After multiple rounds of cycling mutagenesis and DNA shuffling, a more efficient nuclease variant (Sharkey) was generated. In vivo analyses indicated that Sharkey is >15-fold more active than wild-type FCD on a diverse panel of cleavage sites. Further, a mammalian cell-based assay showed a three to sixfold improvement in targeted mutagenesis for ZFNs containing derivatives of the Sharkey cleavage domain. We also identified mutations that impart sequence specificity to the FCD that might be utilized in future studies to further refine ZFNs through cooperative specificity. In addition, Sharkey was observed to enhance the cleavage profiles of previously published and newly selected heterodimer ZFN architectures. This enhanced and highly efficient cleavage domain will aid in a variety of ZFN applications in medicine and biology.