Telomeres, the essential terminal regions of linear eukaryotic chromosomes, consist of G-rich DNA repeats bound by a plethora of associated proteins. While the general pathways of telomere maintenance are evolutionarily conserved, individual telomere complex components show remarkable variation between eukaryotic lineages and even within closely related species. The recent genome sequencing of the lycophyte Selaginella moellendorffii and the availability of an ever-increasing number of flowering plant genomes provides a unique opportunity to evaluate the molecular and functional evolution of telomere components from the early evolving non-seed plants to the more developmentally advanced angiosperms. Here we analyzed telomere sequence in S. moellendorffii and found it to consist of TTTAGGG repeats, typical of most plants. Telomere tracts in S. moellendorffii range from 1 to 5.5 kb, closely resembling Arabidopsis thaliana. We identified several S. moellendorffii genes encoding sequence homologs of proteins involved in telomere maintenance in other organisms, including CST complex components and the telomere-binding proteins, POT1 and the TRFL family. Notable sequence similarities and differences were uncovered among the telomere-related genes in some of the plant lineages. Taken together, the data indicate that comparative analysis of the telomere complex in early diverging land plants such as S. moellendorffii and green algae will yield important insights into the evolution of telomeres and their protein constituents.