Histamine receptors belonging to the superfamily of G protein-coupled receptors (GPCRs) mediate the diverse biological effects of biogenic histamine. They are classified into four phylogenetically distinct subtypes H1-H4, each with a different binding affinity for histamine and divergent downstream signaling pathways. Here we present the evolutionary history of the histamine receptors using a phylogenetic approach complemented with comparative genomics analyses of the sequences, gene structures, and synteny of gene neighborhoods. The data indicate the earliest emergence of histamine-mediated GPCR signaling by a H2 in a prebilaterian ancestor. The analyses support a revised classification of the vertebrate H3-H4 receptor subtypes. We demonstrate the presence of the H4 across vertebrates, contradicting the currently held notion that H4 is restricted to mammals. These non-mammalian vertebrate H4 orthologs have been mistaken for H3. We also identify the presence of a new H3 subtype (H3B), distinct from the canonical H3 (H3A), and propose that the H3A, H3B, and H4 likely emerged from a H3 progenitor through the 1R/2R whole genome duplications in an ancestor of the vertebrates. It is apparent that the ability of the H1, H2, and H3-4 to bind histamine was acquired convergently. We identified genomic signatures suggesting that the H1 and H3-H4 shared a last common ancestor with the muscarinic receptor in a bilaterian predecessor whereas, the H2 and the α-adrenoreceptor shared a progenitor in a prebilaterian ancestor. Furthermore, site-specific analysis of the vertebrate subtypes revealed potential residues that may account for the functional divergence between them. © 2020 Elsevier Inc.