The phylogeny of Decapoda is contentious and many hypotheses have been proposed based on morphological cladistic analyses. Recent molecular studies, however, yielded contrasting results despite their use of similar data (nuclear and mitochondrial rDNA). Here we present the first application of two nuclear protein-coding genes, phosphoenolpyruvate carboxykinase and sodium-potassium ATPase alpha-subunit, to reconstruct the phylogeny of major infraorders within Decapoda. A total of 64 species representing all infraorders of Pleocyemata were analyzed with five species from Dendrobranchiata as outgroups. Maximum likelihood and Bayesian inference reveal that the Reptantia and all but one infraorder are monophyletic. Thalassinidea, however, is polyphyletic. The nodal support for most of the infraordinal and inter-familial relationships is high. Stenopodidea and Caridea form a clade sister to Reptantia, which comprises two major clades. The first clade, consisting of Astacidea, Achelata, Polychelida and three thalassinidean families (Axiidae, Calocarididae and Eiconaxiidae), corresponds essentially to the old taxon suborder Macrura Reptantia. Polychelida nests within Macrura Reptantia instead of being the most basal reptant as suggested in previous studies. The high level of morphological and genetic divergence of Polychelida from Achelata and Astacidea justifies its infraorder status. The second major reptant clade consists of Anomura, Brachyura and two thalassindean families (Thalassinidae and Upogebiidae). Anomura and Brachyura form Meiura, with moderate support. Notably thalassinidean families are sister to both major reptant clades, suggesting that the stem lineage reptants were thalassinidean-like. Moreover, some families (e.g. Nephropidae, Diogenidae, Paguridae) are paraphyletic, warranting further studies to evaluate their status. The present study ably demonstrates the utility of nuclear protein-coding genes in phylogenetic inference in decapods. The topologies obtained are robust and the two molecular markers are informative across a wide range of taxonomic levels. We propose that nuclear protein-coding genes should constitute core markers for future phylogenetic studies of decapods, especially for higher systematics.