Guanylyl cyclases (GCs) are enzymes that generate cyclic GMP and regulate different physiologic and developmental processes in a number of organisms. GCs possess sequence similarity to class III adenylyl cyclases (ACs) and are present as either membrane-bound receptor GCs or cytosolic soluble GCs. We sought to determine the evolution of GCs using a large-scale bioinformatic analysis and found multiple lineage-specific expansions of GC genes in the genomes of many eukaryotes. Moreover, a few GC-like proteins were identified in prokaryotes, which come fused to a number of different domains, suggesting allosteric regulation of nucleotide cyclase activity. Eukaryotic receptor GCs are associated with a kinase homology domain (KHD), and phylogenetic analysis of these proteins suggest coevolution of the KHD and the associated cyclase domain as well as a conservation of the sequence and the size of the linker region between the KHD and the associated cyclase domain. Finally, we also report the existence of mimiviral proteins that contain putative active kinase domains associated with a cyclase domain, which could suggest early evolution of the fusion of these two important domains involved in signal transduction.