Leukocyte rolling on the endothelium via selectin molecules is an important step in the adhesion cascade, which allows leukocytes in the bloodstream to reach sites of infection. We improve upon Adhesive Dynamics simulations by incorporating deformable microvilli on which adhesion molecules are clustered. As determined in micropipette experiments, microvilli deform like an elastic spring at small forces and a combination of yield and viscous dissipation at high forces. First, we create a modified version of the state diagram for adhesion which includes microvillus deformation, and find four adhesion states-firmly bound; landing; rolling; and no-adhesion. Then, we simulate the effects of receptor clustering on the tips of microvilli, number of adhesion molecules on the cell, and the spring constant of the bonds, within the context of deformable microvilli. We also explore how the microvillus rheology itself controls the dynamics of adhesion. A minimum in rolling velocity occurs at an intermediate value of the microvillus membrane viscosity, remarkably close to the reported physiological value, suggesting that the mechanics of microvilli have evolved ideally for rolling and adhesion of leukocytes. We find that a larger degree of association between the membrane and cytoskeleton leads to slower rolling, and stiffer microvilli result in faster rolling. Decreasing the overall deformability of the microvilli greatly reduces a simulated cell's ability to roll. A comparison to experimental results of in vitro cell rolling agrees with the simulation at low shear rates. Furthermore, simulated rolling trajectories of cells with deformable microvilli display periods of rolling interdispersed with pauses, consistent with that seen in experiments where microvilli were observed to stretch.