In 1969, Fedonkin presented a thesis titled "Biostratigraphy and paleontology of the Late Precambrian deposits of Kharaulakh Mountains, Northern Yakutia (Sakha)" to earn his MSc in Geology from Moscow State University.

He went on to obtain a PhD in Stratigraphy\Paleontology (1978) and a Doctorate of Science in Paleobiology (1985) from the Geological Institute, USSR Academy of Sciences, Moscow for his dissertations on "Precambrian fauna and trace fossils from the Russian Platform north" and "Non-skeletal fauna of the Vendian and its place in the evolution of metazoans", respectively.

In 1971, Fedonkin was a junior scientific researcher at the Geological Institute, USSR Academy of Sciences, Moscow.

Since 1992, Fedonkin has been the Head of the laboratory of Precambrian paleobiology at the Paleontological Institute of the Russian Academy of Sciences, Moscow.

Over his career he has completed field work in Australia, Canada, Norway, Poland, Russia, Spain and the United States.