Production of endonucleolytic double-strand DNA breaks requires separate strand cleavage events. Although catalytic mechanisms for simple, dimeric endonucleases are known, there are many complex nuclease machines that are poorly understood. Here we studied the single polypeptide Type ISP restriction-modification (RM) enzymes, which cleave random DNA between distant target sites when two enzymes collide after convergent ATP-driven translocation. We report the 2.7-Å resolution X-ray crystal structure of a Type ISP enzyme-DNA complex, revealing that both the helicase-like ATPase and nuclease are located upstream of the direction of translocation, an observation inconsistent with simple nuclease-domain dimerization. Using single-molecule and biochemical techniques, we demonstrate that each ATPase remodels its DNA-protein complex and translocates along DNA without looping it, leading to a collision complex in which the nuclease domains are distal. Sequencing of the products of single cleavage events suggests a previously undescribed endonuclease model, where multiple, stochastic strand-nicking events combine to produce DNA scission.