Selectin-mediated leukocyte rolling under flow is an important process in leukocyte recruitment during inflammation. The rolling motion of individual cells has been observed to fluctuate randomly both in vivo and in vitro. This paper presents a stochastic model of the micromechanics of cell rolling and provides an analytical method of treating experimental data. For a homogeneous cell population, the velocity distribution is obtained in an analytical form, which is in good agreement with experimentally determined velocity histograms obtained previously. For a heterogeneous cell population, the model provides a simple, analytical method of separating the contributions of temporal fluctuations and population heterogeneity to the variance of measured rolling velocities. The model also links the mean and variance of rolling velocities to the molecular events underlying the observed cellular motion, allowing characterization of the distribution and release rate of the clusters of molecular bonds that tether the cell to substratum. Applying the model to the analysis of data obtained for neutrophils rolling on an E-selectin-coated surface at a wall shear stress of 1.2 dyn/cm2 yields estimations of the average distance between bond clusters (approximately micron) and the average time duration of a bond cluster resisting the applied fluid force (approximately 0.5 s).