To achieve adaptive and heritable immunity against viruses and other mobile genetic elements, CRISPR-Cas systems must capture and store short DNA fragments (spacers) from these foreign elements into host genomic CRISPR arrays. This process is catalyzed by conserved Cas1/Cas2 integration complexes, but the specific roles of another highly conserved protein linked to spacer acquisition, the Cas4 nuclease, are just now emerging. Here, we show that two Cas4 nucleases (Cas4-1 and Cas4-2) play critical roles in CRISPR spacer acquisition in Pyrococcus furiosus. The nuclease activities of both Cas4 proteins are required to process protospacers to the correct size. Cas4-1 specifies the upstream PAM (protospacer adjacent motif), while Cas4-2 specifies the conserved downstream motif. Both Cas4 proteins ensure CRISPR spacer integration in a defined orientation leading to CRISPR immunity. Collectively, these findings provide in vivo evidence for critical roles of Cas4 nucleases in protospacer generation and functional spacer integration at CRISPR arrays.