CRISPR-Cas systems provide prokaryotes with adaptive immunity against foreign genetic elements, including bacteriophages, by recording DNA-based immunological memories of infection called "spacers." How cells without preexisting immunity survive a rapid lytic infection long enough to acquire a new spacer and utilize it for defense remains a mystery. Here, we show that bacteria exploit the alternative dormant or "lysogenic" life cycle of temperate phages to establish CRISPR-Cas immunity. During a phage infection, immunization rates are significantly enhanced in cells entering lysogeny compared to those undergoing lysis. Furthermore, in the absence of a foreign threat, bacteria can acquire spacers targeting prophages residing within the chromosome. In this case, self-targeting by Cas9 promotes curing of the prophage, allowing immunized cells to avoid autoimmunity. The preferred acquisition of spacers during the establishment and maintenance of lysogeny may explain why most spacers in natural bacterial isolates target temperate phages.