Bacteria and archaea are engaged in a constant arms race to defend against the ever-present threats of viruses and invasion by mobile genetic elements. The most flexible weapons in the prokaryotic defense arsenal are the CRISPR-Cas adaptive immune systems. These systems are capable of selective identification and neutralization of foreign DNA and/or RNA. CRISPR-Cas systems rely on stored genetic memories to facilitate target recognition. Thus, to keep pace with a changing pool of hostile invaders, the CRISPR memory banks must be regularly updated with new information through a process termed CRISPR adaptation. In this Review, we outline the recent advances in our understanding of the molecular mechanisms governing CRISPR adaptation. Specifically, the conserved protein machinery Cas1-Cas2 is the cornerstone of adaptive immunity in a range of diverse CRISPR-Cas systems.