Congenital dyserythropoietic anemia type I (CDA I), is an autosomal recessive disease with macrocytic anemia in which erythroid precursors in the bone marrow exhibit pathognomonic abnormalities including spongy heterochromatin and chromatin bridges. We have shown previously that the CDAN1 gene, which is mutated in CDA I, encodes Codanin-1, a ubiquitously expressed and evolutionarily conserved large protein. Recently, an additional etiologic factor for CDA I was reported, C15Orf41. Mutations in both CDAN1 and C15Orf41 genes results in very similar erythroid phenotype. However, the possible relationships between these two etiologic factors. We demonstrate here that Codanin-1 and C15Orf41 bind to each other, and Codanin-1 overexpression increases the levels of C15Orf41. C15Orf41 protein is mainly nuclear and Codanin-1 overexpression shifts it to the cytoplasm. Phylogenetic analyses demonstrated that even though Codanin-1 is an essential protein in mammals, it was apparently lost from several diverse and unrelated animal taxa. Interestingly, C15Orf41 was eliminated in the exact same animal taxa. To the best of our knowledge this is one of the extreme cases of the Phylogenetic Profiling phenomenon, which strongly suggests common pathways for these two proteins.