A strategy for treating inflammatory disease is to create micro-particles with the adhesive properties of leukocytes. The underlying rheology of deformable adhesive microspheres would be an important factor in the adhesive performance of such particles. In this work the effect of particle deformability on the selectin-mediated rolling of polymer vesicles (polymersomes) is evaluated. The rheology of the polymersome membrane was modulated by cross-linking unsaturated side-chains within the hydrophobic core of the membrane. Increased membrane rigidity resulted in decreased rates of particle recruitment rather than decreased average rolling velocities. Reflective interference contrast microscopy of rolling vesicles confirmed that neither flaccid nor rigid vesicles sustained close contacts with the substrate during rolling adhesion. A variable-shear rate parallel-plate flow chamber was employed to evaluate individual vesicles rolling on substrates under different flow conditions. Analysis of the trajectories of single flaccid vesicles revealed several distinct populations of rolling vesicles; however, some of these populations disappear when the vesicle membranes are made rigid. This work shows that membrane mechanics affects the capture, but not the rolling dynamics, of adherent leuko-polymersomes.