Tumor-initiating cells with reprogramming plasticity and/or de-differentiation attributes have been thought to initiate primary tumor development as well as to regenerate secondary tumors in metastatic organs; however, the molecular mechanisms are not fully understood. We previously found that breast tumor-initiating cell marker, CD44, directs multicellular aggregation and cluster formation of circulating tumor cells (CTCs), which further enhance stemness and survival of such cells, enabling metastatic colonization to the lungs. To further elucidate the molecular network underlying CTC cluster formation, we performed global proteomic profiling and discovered that the tetraspanin protein CD81, which is normally enriched in exosomes (small extracellular vesicles), is a new driver of cancer initiation and metastasis as a facilitator and target of CD44. Loss of CD81 compromises tumorigenicity and mammosphere formation of triple negative breast cancer (TNBC) cells. Assisted by machine learning-based algorithms and mutagenesis approach, we found that CD81 interacts with CD44 on the cellular membrane through their extracellular regions. Notably, genetic knockout of CD44 or CD81 results in loss of both CD81 and CD44 in secreted exosomes, a state which abolishes exosome-induced self-renewal of recipient cells, such as mammosphere formation. In addition, RNA sequencing analysis showed that CD81 knockdown up-regulates expression of a cell differentiation marker, SEMA7a, whose down-regulation partially rescues mammosphere formation inhibition by CD81 depletion. Clinically, CD81 expression was observed in >80% of CTCs and specifically enriched and co-expressed along with CD44 in clustered CTCs of breast cancer patients. Mimicing the phenotypes of CD44 deficiency, loss of CD81 also inhibited tumor cell aggregation and lung metastasis of TNBC in both human and mouse tumor models, supporting the clinical significance of CD81 in association with patient outcomes. Our study highlights a new driving role of CD81 in cancer exosome-induced stemness, clustered CTCs, and metastasis initiation of TNBC, reported for the first time to our knowledge.