Cas4 nucleases constitute a core family of CRISPR (Clustered Regularly Interspaced Short Palindromic Repeats) associated proteins, but little is known about their structure and activity. Here we report the crystal structure of the Cas4 protein Pcal_0546 fromPyrobaculum calidifontis, which revealed a monomeric protein with a RecB-like fold and one [2Fe-2S] cluster coordinated by four conserved Cys residues. Pcal_0546 exhibits metal-dependent 5′ to 3′ exonuclease activity against ssDNA substrates, whereas the Cas4 protein SSO1391 fromSulfolobus solfataricuscan cleave ssDNA in both the 5′ to 3′ and 3′ to 5′ directions. The active site of Pcal_0546 contains a bound metal ion coordinated by the side chains of Asp123, Glu136, His146, and the main chain carbonyl of Ile137. Site-directed mutagenesis of Pcal_0546 and SSO1391 revealed that the residues of RecB motifs II, III and QhXXY are critical for nuclease activity, whereas mutations of the conserved Cys residues resulted in a loss of the iron-sulfur cluster, but had no effect on DNA cleavage. Our results revealed the biochemical diversity of Cas4 nucleases, which can have different oligomeric states, contain [4Fe-4S] or [2Fe-2S] clusters, and cleave single stranded DNA in different directions producing single-stranded DNA overhangs, which are potential intermediates for the synthesis of new CRISPR spacers.