Addressing the origin of axial-patterning machinery is essential for understanding the evolution of animal form. Historically, sponges, a lineage that branched off early in animal evolution, were thought to lack Hox and ParaHox genes, suggesting that these critical axial-patterning genes arose after sponges diverged. However, a recent study has challenged this long-held doctrine by claiming to identify ParaHox genes (Cdx family) in two calcareous sponge species, Sycon ciliatum and Leucosolenia complicata. We reanalyzed the main data sets in this paper and analyzed an additional data set that expanded the number of bilaterians represented and removed outgroup homeodomains. As in the previous study, our Neighbor-Joining analyses of the original data sets recovered a clade that included sponge and Cdx genes, whereas Bayesian analyses placed these sponge genes within the NKL subclass of homeodomains. Unlike the original study, only one of our two maximum-likelihood analyses was congruent with Cdx genes in sponges. Our analyses of our additional data set led to the sponge genes consistently being placed within the NKL subclass of homeodomains regardless of method or model. Our results show more support for these sponge genes belonging to the NKL subclass, and therefore imply that Hox and ParaHox genes arose after Porifera diverged from the rest of animals.