Hox genes are renowned for patterning animal development, with widespread roles in developmental gene regulation. Despite this importance their evolutionary origin remains obscure, due to absence of Hox genes (and their evolutionary sisters, the ParaHox genes) from basal lineages and because the phylogenies of these genes are poorly resolved [1-7]. This has led to debate about whether Hox and ParaHox genes originated coincidently with the origin of animals or instead evolved after the divergence of the earliest animal lineages [7,8]. Here we use genomic synteny and Monte Carlo-based simulations to resolve Hox/ParaHox origins, our approach being independent of poorly resolved homeodomain phylogenies and better able to accommodate gene loss. We show Trox-2 of placozoans occupies a ParaHox locus. In addition, a separate locus sharing synteny and hence homology with human Hox loci exists in the placozoan genome, but without a Hox-like gene in it. We call this second locus a ‘ghost’ Hox locus, because it is homologous to the human Hox loci, but does not itself contain a Hox gene. Extending our approach to sponges, we discover distinct ghost Hox and ParaHox loci. Thus distinct Hox and ParaHox loci were present in the last common ancestor of all living animal lineages.