Trace amines, such as tyramine, beta-phenylethylamine, tryptamine, and octopamine, are present in trace levels in nervous systems and bind a specific family of G-protein-coupled receptors (GPCR), but the function or origin of this system is not well understood. We searched the genomes of several eukaryotic species for receptors similar to the mammalian trace amine (TA) receptor subfamily. We identified 18 new receptors in rodents that are orthologous to the previously known TA-receptors. Remarkably, we found 57 receptors (and 40 pseudogenes) of this type in the zebrafish (Danio rerio), while fugu (Takifugu rubripes) had only eight receptors (and seven pseudogenes). We mapped 47 of the zebrafish TA-receptors on chromosomes using radiation hybrid panels and meiotic mapping. The results, together with the degree of conservation and phylogenetic relationships displayed among the zebrafish receptors suggest that the family arose through several different mechanisms involving tetraploidization, block duplications, and local duplication events. Interestingly, these vertebrate TA-receptors do not show a close evolutionary relationship to the invertebrate TA-binding receptors in fruitfly (Drosophila melanogaster), indicating that the ability to bind TA have evolved at least twice in animal evolution. We collected in total over 100 vertebrate TA-receptor sequences, and our phylogenetic analysis shows that several TA-receptors have evolved rapidly with remarkable species variation and that the common ancestor of vertebrate TA-receptors arose before the split of the ray-finned and lobe-finned fishes. The evolutionary history of the TA-receptors is more complex than for most other GPCR families and here we suggest a mechanism by which they may have arisen.