The ability of adherent cells to sense changes in the mechanical properties of their extracellular environments is critical to numerous aspects of their physiology. It has been well documented that cell attachment and spreading are sensitive to substrate stiffness. Here we demonstrate that this behavior is actually biphasic, with a transition that occurs around a Young’s modulus of ~7 kPa. Furthermore, we demonstrate that, contrary to established assumptions, this property is independent of myosin II activity. Rather, we find that cell spreading on soft substrates is inhibited due to reduced nascent adhesion formation within the lamellipodium. Cells on soft substrates display normal leading edge protrusion activity, but these protrusions are not stabilized due to impaired adhesion assembly. Enhancing integrin-ECM affinity through addition of Mn2+ recovers nascent adhesion assembly and cell spreading on soft substrates. Using a computational model to simulate nascent adhesion assembly, we find that biophysical properties of the integrin-ECM bond are optimized to stabilize interactions above a threshold matrix stiffness that is consistent with the experimentally observations. Together these results suggest that myosin II-independent forces in the lamellipodium are responsible for mechanosensation by regulating new adhesion assembly, which in turn, directly controls cell spreading. This myosin II-independent mechanism of substrate stiffness sensing could potentially regulate a number of other stiffness sensitive processes.