Cell recognition and adhesion involving many kinds of cell surface molecules operate via homotypic and/or heterotypic protein-protein and protein-carbohydrate binding. Our investigations in marine sponges have provided direct evidence for a novel molecular mechanism of multivalent glycan-glycan binding related to cellular interactions. Biochemical characterization of purified proteoglycans revealed the presence of specific acidic glycans, different from classical glycosaminoglycans. Such acidic glycans of high molecular weight, containing fucose, glucuronic or galacturonic acids, and pyruvate and sulfate groups may represent a new class of primordial proteoglycans, named by us glyconectins. The thermodynamic and kinetic approaches of biological macromolecule interactions do not provide a direct measurement of the intermolecular binding forces that are fundamental for the function of the ligand-receptor association. Using the atomic force microscopy (AFM), we provided the first quantitative evaluation of the binding strength between cell adhesion proteoglycans. Measurement of binding forces intrinsic to cell adhesion glyconectin proteoglycans (AGPs) is necessary to assess their contribution to the maintenance of the anatomical integrity of multicellular organisms. (i) As a model, we selected the cell AGP isolated from the marine sponge Microciona prolifera; it mediates in vivo cell recognition and aggregation via homotypic, species-specific, multivalent, and calcium ion-dependent glycan-glycan interactions. (ii) Under physiological conditions, a large cohesive force theoretically able to hold the weight of approximately 1600 cells was measured. (iii) The C-2 autocomplementarity model for AGP-AGP interactions; and (iv) the requirement of the calcium ionic bridges suggest also that the self-recognition and multivalency of glycan-glycan interactions are essential for cell adhesion. (v) The evolution of glyconectin-like proteoglycan molecules may have been a fundamental prerequisite for the emergence of the first multicellular organisms. Glycan-glycan interactions may thus provide a new paradigm for molecular self-recognition.