Background The ParaHox gene cluster is the evolutionary sister to the Hox cluster. Whilst the role of the Hox cluster in patterning the anterior-posterior axis of bilaterian animals is well established, and the organisation of vertebrate Hox clusters is intimately linked to gene regulation, much less is known about the more recently discovered ParaHox cluster. ParaHox gene clustering, and its relationship to expression, has only been described in deuterostomes. Conventional protostome models (Drosophila melanogaster and Caenorhabditis elegans) are secondarily derived with respect to ParaHox genes, suffering gene loss and cluster break-up. Results We provide the first evidence for ParaHox gene clustering from a less-derived protostome animal, the annelid Platynereis dumerilii. Clustering of these genes is thus not a sole preserve of the deuterostome lineage within Bilateria. This protostome ParaHox cluster is not entirely intact however, with Pdu-Cdx being on the opposite end of the same chromosome arm from Pdu-Gsx and Pdu-Xlox. From the genomic sequence around the P. dumerilii ParaHox genes the neighbouring genes are identified, compared with other taxa, and the ancestral arrangement deduced. Conclusion We relate the organisation of the ParaHox genes to their expression, and from comparisons with other taxa hypothesise that a relatively complex pattern of ParaHox gene expression existed in the protostome-deuterostome ancestor, which was secondarily simplified along several invertebrate lineages. Detailed comparisons of the gene content around the ParaHox genes enables the reconstruction of the genome surrounding the ParaHox cluster of the protostome-deuterostome ancestor, which existed over 550 million years ago.