Pyrococcus abyssi NucS is the founding member of a new family of structure-specific DNA endonucleases that interact with the replication clamp proliferating cell nuclear antigen (PCNA). Using a combination of small angle x-ray scattering and surface plasmon resonance analyses, we demonstrate the formation of a stable complex in solution, in which one molecule of the PabNucS homodimer binds to the outside surface of the PabPCNA homotrimer. Using fluorescent labels, PCNA is shown to increase the binding affinity of NucS toward single-strand/double-strand junctions on 5′ and 3′ flaps, as well as to modulate the cleavage specificity on the branched DNA structures. Our results indicate that the presence of a single major contact between the PabNucS and PabPCNA proteins, together with the complex-induced DNA bending, facilitate conformational flexibility required for specific cleavage at the single-strand/double-strand DNA junction. © 2012 by The American Society for Biochemistry and Molecular Biology, Inc.