DNA replication is one of the most ancient of cellular processes and functional similarities among its molecular machinery are apparent across all cellular life. Cdc45 is one of the essential components of the eukaryotic replication fork and is required for the initiation and elongation of DNA replication, but its molecular function is currently unknown. In order to trace its evolutionary history and to identify functional domains, we embarked on a computational sequence analysis of the Cdc45 protein family. Our findings reveal eukaryotic Cdc45 and prokaryotic RecJ to possess a common ancestry and Cdc45 to contain a catalytic site within a predicted exonuclease domain. The likely orthology between Cdc45 and RecJ reveals new lines of enquiry into DNA replication mechanisms in eukaryotes.