NK cells and CD8+ T cells exhibit cytotoxicity and cytokine production upon recognizing target cells through cell-cell interaction. We screened the molecules involved in the recognition and regulation of these cells using cDNA subtraction between naive and activated NK cells. We identified class I-restricted T cell-associated molecule (CRTAM), a two Ig domain-bearing surface receptor, as a molecule rapidly and transiently expressed on NK cells and CD8+ T cells upon activation. CRTAM is expressed as a dimer on the cell surface, and its expression is transcriptionally regulated. Using an expression-cloning system, we then further identified Nectin-like (Necl) molecule 2, a three Ig domain-containing receptor, as a ligand of CRTAM. While Necl2 mediates homotypic interaction, CRTAM interacts with Necl2 but not with CRTAM itself. The heterotypic CRTAM-Necl2 interaction has a higher affinity than the homotypic Necl2 interaction. Although there was no clear alteration in the cytotoxic function of the NK cells and CD8+ T cells against the Necl2-expressing target cells, T cells expressing CRTAM tightly bound to Necl2-expressing cells. CRTAM+ cells did not induce homotypic aggregation but they did exert strong heterotypic binding with Necl2+ cells, which was inhibited by the addition of the CRTAM-Ig fusion protein. These results suggest that the heterotypic interaction between CRTAM and Necl2 plays an important role in the adhesion, interaction or migration of NK cells and CD8+ T cells upon stimulation.