The Agouti-like peptides including AgRP, ASIP and the teleost-specific A2 (ASIP2 and AgRP2) peptides have potent and diverse functional roles in feeding, pigmentation and background adaptation mechanisms. There are contradictory theories about the evolution of the Agouti-like peptide family as well the nomenclature. Here we performed comprehensive mining and annotation of vertebrate Agouti-like sequences. We identified A2 sequences from salmon, trout, seabass, cod, cichlid, tilapia, gilt-headed sea bream, Antarctic toothfish, rainbow smelt, common carp, channel catfish and interestingly also in lobe-finned fish. Moreover, we surprisingly found eight novel homologues from the kingdom of arthropods and three from fungi, some sharing the characteristic C-x(6)-C-C motif which are present in the Agouti-like sequences, as well as approximate sequence length (130 amino acids), positioning of the motif sequence and sharing of exon-intron structures that are similar to the other Agouti-like peptides providing further support for the common origin of these sequences. Phylogenetic analysis shows that the AgRP sequences cluster basally in the tree, suggesting that these sequences split from a cluster containing both the ASIP and the A2 sequences. We also used a novel approach to determine the statistical evidence for synteny, a sinusoidal Hough transform pattern recognition technique. Our analysis shows that the teleost AgRP2 resides in a chromosomal region that has synteny with Hsa 8, but we found no convincing synteny between the regions that A2, AgRP and ASIP reside in, which would support that the Agouti-like peptides were formed by whole genome tetraplodization events. Here we suggest that the Agouti-like peptide genes were formed through classical subsequent gene duplications where the AgRP is the most distantly related to the three other members of that group, first splitting from a common ancestor to ASIP and A2, and then later the A2 split from ASIP followed by a split resulting in ASIP2 and AgRP2.