Uracil-DNA glycosylase (UDG) is an important repair enzyme in all organisms to remove uracil bases from DNA. Recent biochemical studies have revealed that human nuclear UDG (UNG2) forms a multiprotein complex in replication foci and initiates the base excision repair pathway by interacting with proliferating cell nuclear antigen (PCNA). Here, we show the physical and functional interactions between UDG and PCNA from the hyperthermophilic euryarchaeon, Pyrococcus furiosus. The physical interaction between the two proteins was identified by a surface plasmon resonance analysis. Furthermore, the uracil glycosylase activity of P. furiosus UDG is stimulated by P. furiosus PCNA (PfuPCNA) in vitro. This stimulatory effect was observed only when wild type PfuPCNA, but not a monomeric PCNA mutant, was present in the reaction. Mutational analyses revealed that our predicted PCNA-binding region (AKTLF) in P. furiosus UDG is actually important for the interaction with PfuPCNA. This is the first report describing the functional interaction between archaeal UDG and PCNA.