The reliability of evolutionary reconstructions based on the fossil record critically depends on our knowledge of the factors affecting the fossilization of soft-bodied organisms. Despite considerable research effort, these factors are still poorly understood. The extreme rarity of unicellular non-skeletal eukaryotic fossils compared to multicellular ones is an example of a pattern that apparently requires taphonomic explanation. In order to elucidate the main prerequisites for the preservation of soft-bodied organisms, we conducted long-term (1-5 years) taphonomic experiments with the model crustacean Artemia salina buried in five different sediments. The subsequent analysis of the carcasses and sediments revealed that, in our experimental settings, better preservation was associated with the fast deposition of aluminium and silicon on organic tissues. Other elements such as calcium, magnesium and iron, which can also accumulate quickly on the carcasses, appear to be much less efficient in preventing decay. Next, we asked if the carcasses of uni- and multicellular organisms differ in their ability to accumulate aluminium ions on their surface. The experiments with the flagellate Euglena gracilis and the sponge Spongilla lacustris showed that aluminium ions are more readily deposited onto a multicellular body. This was further confirmed by the experiments with uni- and multicellular stages of the social amoeba Dictyostelium discoideum. The results lead us to speculate that the evolution of cell adhesion molecules, which provide efficient cell-cell and cell-substrate binding, probably can explain the rich fossil record of multicellular soft-bodied organisms, the poor fossil record of non-skeletal unicellular eukaryotes, and the explosive emergence of the Cambrian diversity of soft bodied fossils.