The telomere repeat units of Candida species are substantially longer and more complex than those in other organisms, raising interesting questions concerning the recognition mechanisms of telomere-binding proteins. Herein we characterized the properties of Candida parapsilosis Cdc13A and Cdc13B, two paralogs that are responsible for binding and protecting the telomere G-strand tails. We found that Cdc13A and Cdc13B can each form complexes with itself and a heterodimeric complex with each other. However, only the heterodimer exhibits high-affinity and sequence-specific binding to the telomere G-tail. EMSA and crosslinking analysis revealed a combinatorial mechanism of DNA recognition, which entails the A and B subunit making contacts to the 3' and 5' region of the repeat unit. While both the DBD and OB4 domain of Cdc13A can bind to the equivalent domain in Cdc13B, only the OB4 complex behaves as a stable heterodimer. The unstable Cdc13AB(DBD) complex binds G-strand with greatly reduced affinity but the same sequence specificity. Thus the OB4 domains evidently contribute to binding by promoting dimerization of the DBDs. Our investigation reveals a rare example of combinatorial recognition of single-stranded DNA and offers insights into the co-evolution of telomere DNA and cognate binding proteins.