Telomeres must be capped to preserve chromosomal stability. The conserved Stn1 and Ten1 proteins are required for proper capping of the telomere, although the mechanistic details of how they contribute to telomere maintenance are unclear. Here, we report the crystal structures of the C-terminal domain of the Saccharomyces cerevisiae Stn1 and the Schizosaccharomyces pombe Ten1 proteins. These structures reveal striking similarities to corresponding subunits in the replication protein A complex, further supporting an evolutionary link between telomere maintenance proteins and DNA repair complexes. Our structural and in vivo data of Stn1 identify a new domain that has evolved to support a telomere-specific role in chromosome maintenance. These findings endorse a model of an evolutionarily conserved mechanism of DNA maintenance that has developed as a result of increased chromosomal structural complexity.