Many proteins exist in the so-called "twilight zone" of sequence alignment, where low pairwise sequence identity makes it difficult to determine homology and phylogeny. ¹ ^, ² As protein tertiary structure is often more conserved, ³ recent advances in ab initio protein folding have made structure-based identification of putative homologs feasible. ⁴ ^, ⁵ ^, ⁶ We present a pipeline for the identification and characterization of distant homologs and apply it to 7-transmembrane-domain ion channels (7TMICs), a protein group founded by insect odorant and gustatory receptors. Previous sequence and limited structure-based searches identified putatively related proteins, mainly in other animals and plants. ⁷ ^, ⁸ ^, ⁹ ^, ¹⁰ However, very few 7TMICs have been identified in non-animal, non-plant taxa. Moreover, these proteins' remarkable sequence dissimilarity made it uncertain whether disparate 7TMIC types (Gr/Or, Grl, GRL, DUF3537, PHTF, and GrlHz) are homologous or convergent, leaving their evolutionary history unresolved. Our pipeline identified thousands of new 7TMICs in archaea, bacteria, and unicellular eukaryotes. Using graph-based analyses and protein language models to extract family-wide signatures, we demonstrate that 7TMICs have structure and sequence similarity, supporting homology. Through sequence- and structure-based phylogenetics, we classify eukaryotic 7TMICs into two families (Class-A and Class-B), which are the result of a gene duplication predating the split(s) leading to Amorphea (animals, fungi, and allies) and Diaphoretickes (plants and allies). Our work reveals 7TMICs as a cryptic superfamily, with origins close to the evolution of cellular life. More generally, this study serves as a methodological proof of principle for the identification of extremely distant protein homologs.