CRISPR-Cas systems adapt their immunological memory against their invaders by integrating short DNA fragments into clustered regularly interspaced short palindromic repeat (CRISPR) loci. While Cas1 and Cas2 make up the core machinery of the CRISPR integration process, various class I and II CRISPR-Cas systems encode Cas4 proteins for which the role is unknown. Here, we introduced the CRISPR adaptation genes cas1, cas2, and cas4 from the type I-D CRISPR-Cas system of Synechocystis sp. 6803 into Escherichia coli and observed that cas4 is strictly required for the selection of targets with protospacer adjacent motifs (PAMs) conferring I-D CRISPR interference in the native host Synechocystis. We propose a model in which Cas4 assists the CRISPR adaptation complex Cas1-2 by providing DNA substrates tailored for the correct PAM. Introducing functional spacers that target DNA sequences with the correct PAM is key to successful CRISPR interference, providing a better chance of surviving infection by mobile genetic elements. Kieper et al. demonstrate that the ubiquitous protein Cas4 assists Cas1 and Cas2 in the selection of new CRISPR spacers with a PAM licensing efficient CRISPR interference.