Mechanical cues are sensed and transduced by cell adhesion complexes to regulate diverse cell behaviors. Extracellular matrix (ECM) rigidity sensing by integrin adhesions has been well studied, but rigidity sensing by cadherins during cell adhesion is largely unexplored. Using mechanically tunable polyacrylamide (PA) gels functionalized with the extracellular domain of E-cadherin (Ecad-Fc), we showed that E-cadherin-dependent epithelial cell adhesion was sensitive to changes in PA gel elastic modulus that produced striking differences in cell morphology, actin organization, and membrane dynamics. Traction force microscopy (TFM) revealed that cells produced the greatest tractions at the cell periphery, where distinct types of actin-based membrane protrusions formed. Cells responded to substrate rigidity by reorganizing the distribution and size of high-traction-stress regions at the cell periphery. Differences in adhesion and protrusion dynamics were mediated by balancing the activities of specific signaling molecules. Cell adhesion to a 30-kPa Ecad-Fc PA gel required Cdc42- and formin-dependent filopodia formation, whereas adhesion to a 60-kPa Ecad-Fc PA gel induced Arp2/3-dependent lamellipodial protrusions. A quantitative 3D cell-cell adhesion assay and live cell imaging of cell-cell contact formation revealed that inhibition of Cdc42, formin, and Arp2/3 activities blocked the initiation, but not the maintenance of established cell-cell adhesions. These results indicate that the same signaling molecules activated by E-cadherin rigidity sensing on PA gels contribute to actin organization and membrane dynamics during cell-cell adhesion. We hypothesize that a transition in the stiffness of E-cadherin homotypic interactions regulates actin and membrane dynamics during initial stages of cell-cell adhesion.