Through elegant studies in fungal cells and complex organisms, we propose a unifying paradigm for the rapid evolution of telomere binding proteins (TBPs) that associate with either (or both) telomeric DNA and telomeric proteins. TBPs protect and regulate telomere structure and function. Four critical factors are involved. First, TBPs that commonly bind to telomeric DNA include the c-Myb binding proteins, OB-fold single-stranded binding proteins, and G-G base paired Hoogsteen structure (G4) binding proteins. Each contributes independently or, in some cases, cooperatively, to provide a minimum level of telomere function. As a result of these minimal requirements and the great abundance of homologs of these motifs in the proteome, DNA telomere-binding activity may be generated more easily than expected. Second, telomere dysfunction gives rise to genome instability, through the elevation of recombination rates, genome ploidy, and the frequency of gene mutations. The formation of paralogs that diverge from their progenitor proteins ultimately can form a high frequency of altered TBPs with altered functions. Third, TBPs that assemble into complexes (e.g., mammalian shelterin) derive benefits from the novel emergent functions. Fourth, a limiting factor in the evolution of TBP complexes is the formation of mutually compatible interaction surfaces amongst the TBPs. These factors may have different degrees of importance in the evolution of different phyla, illustrated by the apparently simpler telomeres in complex plants. Selective pressures that can utilize the mechanisms of paralog formation and mutagenesis to drive TBP evolution along routes dependent on the requisite physiologic changes.