Phylogenetic relationships among all of the major decapod infraorders have never been estimated using molecular data, while morphological studies produce conflicting results. In the present study, the phylogenetic relationships among the decapod basal suborder Dendrobranchiata and all of the currently recognized decapod infraorders within the suborder Pleocyemata (Caridea, Stenopodidea, Achelata, Astacidea, Thalassinidea, Anomala, and Brachyura) were inferred using 16S mtDNA, 18S and 28S rRNA, and the histone H3 gene. Phylogenies were reconstructed using the model-based methods of maximum likelihood and Bayesian methods coupled with Markov Chain Monte Carlo inference. The phylogenies revealed that the seven infraorders are monophyletic, with high clade support values (bp>70; pP>0.95) under both methods. The two suborders also were recovered as monophyletic, but with weaker support (bp=70; pP=0.74). Although the nodal support values for infraordinal relationships were low (bp<50; pP<0.77) the Anomala and Brachyura were basal to the rest of the 'Reptantia' in both reconstructions and using Bayesian tree topology tests alternate morphology-based hypotheses were rejected (P<0.01). Newly developed multi-locus Bayesian and likelihood heuristic rate-smoothing methods to estimate divergence times were compared using eight fossil and geological calibrations. Estimated times revealed that the Decapoda originated earlier than 437MYA and that the radiation within the group occurred rapidly, with all of the major lineages present by 325MYA. Node time estimation under both approaches is severely affected by the number and phylogenetic distribution of the fossil calibrations chosen. For analyses incorporating fossils as fixed ages, more consistent results were obtained by using both shallow and deep or clade-related calibration points. Divergence time estimation using fossils as lower and upper limits performed well with as few as one upper limit and a single deep fossil lower limit calibration.