Hox and ParaHox (H/P) genes belong to evolutionary-sister clusters that arose through duplication of a ProtoHOX cluster early in animal evolution. In contrast to bilaterians, cnidarians express, beside PG1, PG2 and Gsx orthologs, numerous Hox-related genes with unclear origin. We characterized from marine hydrozoans three novel Hox-related genes expressed at medusa and polyp stages, which include a Pdx/Xlox ParaHox ortholog induced 1 day later than Gsx during embryonic development. To reconstruct H/P genes' early evolution, we performed multiple systematic comparative phylogenetic analyses, which identified derived sequences that blur the phylogenetic picture, recorded dramatically different evolutionary rates between ParaHox and Hox in cnidarians and showed the unexpected grouping of [Gsx-Pdx/Xlox-PG2-PG3] families in a single metagroup distinct from PG1. We propose a novel more parsimonious evolutionary scenario whereby H/P genes originated from a [Gsx-Pdx/Xlox-PG2-PG3]-related ProtoHox gene, the "posterior" and "anterior" H/P genes appearing secondarily. The ProtoHOX cluster would have contained the three Gsx/PG2, Pdx/PG3, Cdx/PG9 paralogs and produced through tandem duplication the primordial HOX and ParaHOX clusters in the Cnidaria-Bilateria ancestor. The stronger constraint on cnidarian ParaHox genes suggests that the primary function of pre-bilaterian H/P genes was to drive cellular evolutionary novelties such as neurogenesis rather than axis specification.