Increased size of eukaryotic genomes necessitated the use of multiple origins of DNA replication, and presumably selected for their efficient spacing to ensure rapid DNA replication. The sequence of these origins remains undetermined in metazoan genomes, leaving important questions about the selective constraints acting on replication origins unanswered. We have chosen to study the evolution of proteins that recognize and define these origins every cell cycle, as a surrogate to the direct analysis of replication origins. Among these DNA replication proteins is the essential Cdc6 protein, which acts to license origins for replication. We find that two different species pairs of Drosophila show evidence of positive selection in Cdc6 in their highly conserved C-terminal AAA-ATPase domain. We also identified amino acid segments that are highly conserved in the N-terminal tail of Cdc6 proteins from various Drosophila species, but are not conserved even in closely related insect species. Instead, we find that the N-terminal tails of Cdc6 proteins vary extensively in size and sequence across different eukaryotic lineages. Our results suggest that choice of origin firing may be significantly altered in closely related species, as each set of replication proteins optimizes to its own genomic landscape.