An evolutionary tree of key enzymes from the Complex-Iron-Sulfur-Molybdoenzyme (CISM) superfamily distinguishes “ancient” members, i.e. enzymes present already in the last universal common ancestor (LUCA) of prokaryotes, from more recently evolved subfamilies. The majority of the presented subfamilies and, as a consequence, the Molybdo-enzyme superfamily as a whole, appear to have existed in LUCA.
I believe many people know that some enzymes have molybdenum cofactors. But, I highly doubt that many are aware of the fact that tungsten can also be found in some enzymes. Which one came first though? What are the differences between them in terms of solubility for example? The real interesting part is that both molybdenum and tungsten are produced in supernova explosions. So when did they come? How did they come here? how did they affect the life on earth? Well not all the answers are known yet, but here is a nice paper on molybdenum and tungsten enzymes.
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3278043/