Context : Primordial molecules were formed during the Dark Ages , i.e . the time between recombination and reionization in the early Universe . They were the constitutents of the first proto-stellar clouds . Standard Big Bang nucleosynthesis predicts the abundances of hydrogen , helium , lithium , beryllium , and their isotopes in the early Universe . Heavier nuclei such as carbon , nitrogen , or oxygen are formed in trace amounts only . In non-standard Big Bang nucleosynthesis models , it is possible to synthesize larger quantities of these heavier elements . The latter are interesting because they can form molecules with a high electric dipole moment which can increase the cooling in collapsing protostellar structures . Aims : The purpose of this article is to analyze the formation of primordial molecules based on heavy elements during the Dark Ages , with elemental abundances taken from different nucleosynthesis models . Methods : We present calculations of the full non-linear equation set governing the primordial chemistry . We consider the evolution of 45 chemical species and use an implicit multistep method of variable order of precision with an adaptive stepsize control . Results : For the first time the cosmological recombination of heavy elements is presented . We find that the most abundant Dark Ages molecules based on heavy elements are CH and OH . When considering initial conditions given by the standard Big Bang nucleosynthesis model , we obtain relative abundances \mathrm { [ CH ] } = n _ { \mathrm { CH } } / n _ { \mathrm { b } } = 6.2 \times 10 ^ { -21 } and \mathrm { [ OH ] } = n _ { \mathrm { OH } } / n _ { \mathrm { b } } = 1.2 \times 10 ^ { -23 } at z = 10 , where n _ { \mathrm { b } } is the total number density . But non-standard nucleosynthesis can lead to higher heavy element abundances while still satisfying the observed primordial light abundances . In that case , we show that the abundances of molecular species based on C , N , O and F can be enhanced by two orders of magnitude , leading to a CH relative abundance higher than that of HD ^ { + } or H _ { 2 } D ^ { + } . Conclusions :