Hox and other Antennapedia (ANTP)-like homeobox gene subclasses-ParaHox, EHGbox, and NK-likecontribute to key developmental events in bilaterians [1-4]. Evidence of physical clustering of ANTP genes in multiple animal genomes [4-9] suggests that all four subclasses arose via sequential cis-duplication events. Here, we show that Hox genes’origin occurred after the divergence of sponge and eumetazoan lineages and occurred concomitantly with a major evolutionary transition in animal body-plan complexity. By using whole genome information from the demosponge Amphimedon queenslandica, we provide the first conclusive evidence that the earliest metazoans possessed multiple NK-like genes but no Hox, ParaHox, or EHGbox genes. Six of the eight NK-like genes present in the Amphimedon genome are clustered within 71 kb in an order akin to bilaterian NK clusters. We infer that the NK cluster in the last common ancestor to sponges, cnidarians, and bilaterians consisted of at least five genes. It appears that the ProtoHox gene originated from within this ancestral cluster after the divergence of sponge and eumetazoan lineages. The maintenance of the NK cluster in sponges and bilaterians for greater than 550 million years is likely to reflect regulatory constraints inherent to the organization of this ancient cluster.