Multicellular animals, or Metazoa, appear in the fossil records between 575 and 509 million years ago (MYA). At odds with paleontological evidence, molecular estimates of basal metazoan divergences have been consistently older than 700 MYA. However, those date estimates were based on the molecular clock hypothesis, which is almost always violated. To relax this hypothesis, we have implemented a Bayesian approach to describe the change of evolutionary rate over time. Analysis of 22 genes from the nuclear and the mitochondrial genomes under the molecular clock assumption produced old date estimates, similar to those from previous studies. However, by allowing rates to vary in time and by taking small species-sampling fractions into account, we obtained much younger estimates, broadly consistent with the fossil records. In particular, the date of protostome-deuterostome divergence was on average 582 +/- 112 MYA. These results were found to be robust to specification of the model of rate change. The clock assumption thus had a dramatic effect on date estimation. However, our results appeared sensitive to the prior model of cladogenesis, although the oldest estimates (791 +/- 246 MYA) were obtained under a suboptimal model. Bayes posterior estimates of evolutionary rates indicated at least one major burst of molecular evolution at the end of the Precambrian when protostomes and deuterostomes diverged. We stress the importance of assumptions about rates on date estimation and suggest that the large discrepancies between the molecular and fossil dates of metazoan divergences might partly be due to biases in molecular date estimation.