Prokaryotic adaptive immunity is established against mobile genetic elements (MGEs) by 'naïve adaptation' when DNA fragments from a newly encountered MGE are integrated into CRISPR-Cas systems. In Escherichia coli, DNA integration catalyzed by Cas1-Cas2 integrase is well understood in mechanistic and structural detail but much less is known about events prior to integration that generate DNA for capture by Cas1-Cas2. Naïve adaptation in E. coli is thought to depend on the DNA helicase-nuclease RecBCD for generating DNA fragments for capture by Cas1-Cas2. The genetics presented here show that naïve adaptation does not require RecBCD nuclease activity but that helicase activity may be important. RecA loading by RecBCD inhibits adaptation explaining previously observed adaptation phenotypes that implicated RecBCD nuclease activity. Genetic analysis of other E. coli nucleases and naïve adaptation revealed that 5' ssDNA tailed DNA molecules promote new spacer acquisition. We show that purified E. coli Cas1-Cas2 complex binds to and nicks 5' ssDNA tailed duplexes and propose that E. coli Cas1-Cas2 nuclease activity on such DNA structures supports naïve adaptation.