The explosion of genomics permits investigations into the origin and early evolution of the Metazoa at the molecular level. In this thesis, I am particularly interested in investigating the molecular foundation of the animal senses (i.e. how animals perceive their world). To understand the directionality of evolutionary innovation a well-developed phylogenetic framework is necessary. On one hand, the combination of molecular and morphological data sets has revolutionized our views of metazoan relationships over the past decades, but on the other hand, a number of nodes on the metazoan tree remain uncertain. Uncertainty is particularly high with reference to the taxa generally named “early branching metazoans”. Unfortunately, understanding the relationships among these taxa is key to understanding the evolution of sensory perception (Nielsen 2008). In this thesis I will investigate both animal phylogenetics (to attempt to resolve the phylogeny among the early branching Metazoa) and the evolution of the metazoan sensory receptors. The G-protein coupled receptor superfamily (GPCR) superfamily is the main family of metazoan surface receptors. In this thesis, after an initial introduction (Chapter 1), I address and substantially clarify the relationship among the early branching animals (Chapter 2) using novel genomic data and publicly available expressed sequence tags (ESTs). I then move forward (Chapter 3) to use network-based methods to study the early evolution of the GPCR superfamily in Eukaryotes and animals. Finally (Chapter 4), I focus on the study of a specific subset of GPCRs (the a-group, Rhodopsin-like receptors). This GPCR group is particularly interesting as it includes the best studied and, arguably, one of the most interesting among the GPCR families: the Opsin family. Opsins are key proteins used in the process of light detection, and the origin and early evolution of this family are still substantially unknown. Chapter 4 addresses both these problems. The thesis is then concluded by a general discussion (Chapter 5) and a future directions (Chapter 6) section. Overall, this thesis provides new insights into the origin and early evolution of the Metazoa and their senses.