Replication Protein A (RPA) is a heterotrimeric single stranded DNA-binding protein with essential roles in DNA replication, recombination and repair. Little is known about the structure of RPA in Archaea, the third domain of life. By using an integrative structural, biochemical and biophysical approach, we extensively characterize RPA from Pyrococcus abyssi in the presence and absence of DNA. The obtained X-ray and cryo-EM structures reveal that the trimerization core and interactions promoting RPA clustering on ssDNA are shared between archaea and eukaryotes. However, we also identified a new domain, which may be important for regulating the RPA dissociation, and show that RPA forms an unanticipated tetrameric supercomplex that recruits the DNA primase, and may contribute to the efficient synthesis of Okazaki fragments in Archaea. Our results provide new insight into the evolution of this primordial replication factor in eukaryotes.