Telomeres are nucleoprotein structures at the ends of linear eukaryotic chromosomes. The specific DNA structures are exposed to the so-called end-replication and end-protection problems. Proteins that bind specifically to the unique sequences of telomeres aid in solving these problems. In vertebrates, the core protective complex is called shelterin and supports telomere maintenance and protection with its several subunits. Similar complexes guarding and maintaining telomeric DNA have been described in many other species such as Saccharomyces cerevisiae, Schizosaccharomyces pombe, Arabidopsis thaliana or Drosophila melanogaster. In this study, we aimed at identifying and characterizing previously unknown telomeric factors in the model organism Caenorhabditis elegans. Utilizing quantitative proteomics coupled to a DNA pulldown experiment performed with nuclear extract of C. elegans, we identified a set of proteins associating with telomeres. In this set of proteins, we detected previously described telomere binders, proteins that were described in other functions and proteins that had no reported functions. This suggests more potential interactors at C. elegans telomeres then previously reported. Among the set of identified proteins, we focused on the paralog proteins R06A4.2 and T12E12.3 and further characterized their function at C. elegans telomeres. A validation of binding in vivo and in vitro showed association of the proteins to the double-stranded telomere in a nanomolar range and colocalization with a known telomere binder, POT-1. Interestingly, despite sharing a high percentage of amino acid and nucleotide sequence identity, animals with a mutation in either gene show divergent phenotypes. While deletion of R06A4.2 leads to telomere elongation, deletion of T12E12.3 leads to shorter telomeres and a mortal germline phenotype. We show that a double mutant of both proteins leads to immediate synthetic sterility in the first homozygous generation, with an obvious underdevelopment of the germline. Furthermore, we show with different biochemical approaches that R06A4.2 and T12E12.3 interact not only with each other at specific times in C. elegans development, but additionally interact with the previously reported single-strand telomere binders POT-1, POT-2 and MRT-1. In addition, we could demonstrate that a homolog of the candidate proteins in C. briggsae is also interacting with telomeres, giving the proteins a potential conserved function throughout the Caenorhabditis genus. Altogether, our data provides indication for the first described complex of telomere binding proteins in C. elegans, involving the first reliably described telomere double-strand binders R06A4.2 and T12E12.3.