The transition from unicellular to multicellular organisms poses the question as to when genes that regulate cell-cell interactions emerged during evolution. The receptor and ligand pairing of plexins and semaphorins regulates cellular interactions in a wide range of developmental and physiological contexts. We surveyed here genomes of unicellular eukaryotes and of non-bilaterian and bilaterian Metazoa and performed phylogenetic analyses to gain insight into the evolution of plexin and semaphorin families. Remarkably, we detected plexins and semaphorins in unicellular choanoflagellates, indicating their evolutionary origin in a common ancestor of Choanoflagellida and Metazoa. The plexin domain structure is conserved throughout all clades; in contrast, semaphorins are structurally diverse. Choanoflagellate semaphorins are transmembrane proteins with multiple fibronectin type III domains following the N-terminal Sema domain (termed Sema-FN). Other previously not yet described semaphorin classes include semaphorins of Ctenophora with tandem immunoglobulin domains (Sema-IG) and secreted semaphorins of Echinoderamata (Sema-SP, Sema-SI). Our study also identified Met receptor tyrosine kinases (RTKs), which carry a truncated plexin extracellular domain, in several bilaterian clades, indicating evolutionary origin in a common ancestor of Bilateria. In addition, a novel type of Met-like RTK with a complete plexin extracellular domain was detected in Lophotrochozoa and Echinodermata (termed Met-LP RTK). Our findings are consistent with an ancient function of plexins and semaphorins in regulating cytoskeletal dynamics and cell adhesion that predates their role as axon guidance molecules.