Experimental investigations have demonstrated that cells can actively sense and respond to physical aspects of their environments, such as substrate stiffness of biomaterials, via integrin receptors with the help of stochastic thermal undulations of cell membranes. This paper develops a physical model for the mechanism of integrin-dependent cell-substrate adhesion nucleation in order to investigate the influence of substrate stiffness on primary adhesion formation. In this model, a series of so-called energy potential wells are established to quantitatively describe force-driven conformational changes of integrins on elastic substrates with different rigidities. A concept of nucleation domain is proposed to characterize the necessary condition of integrin-mediated cell-substrate primary adhesion formation. In the framework of classical statistical mechanics, the competitive relationship is investigated between the local thermal undulations of plasma membranes and the conformational conversions of substrate-binding integrins. The quantitative dependence of integrin-mediated adhesion nucleation on substrate rigidities is systematically explored, which shows a reasonable agreement with existing experimental results. (C) 2011 Elsevier Inc. All rights reserved.