Bacillus thuringiensis secretes the virulence factor phosphatidylinositol-specific phospholipase C (BtPI-PLC) which specifically binds to phosphatidylcholine (PC) and cleaves GPI-anchored proteins off eukaryotic plasma membranes. To elucidate how BtPI-PLC searches for GPI-anchored proteins on the membrane surface, we measured residence times of single fluorescently labeled proteins on PC-rich small unilamellar vesicles (SUVs). BtPI-PLC interactions with the SUV surface are transient with a lifetime of 379 ± 49 ms. These data also suggest that BtPI-PLC does not directly sense curvature, but rather prefers to bind to the numerous lipid packing defects in SUVs. Despite this preference for defects, all-atom molecular dynamics (MD) simulations of BtPI-PLC interacting with PC-rich bilayers show that the protein is shallowly anchored with the deepest insertions approximately 18 Å above the bilayer center. Membrane partitioning is mediated, on average, by 41 hydrophobic, 8 hydrogen bond and 2 cation-π (between PC choline headgroups and Tyr residues) transient interactions with phospholipids. These results lead to a quantitative model for BtPI-PLC interactions with cell membranes where protein binding is mediated by lipid packing defects, possibly near GPI-anchored proteins, and the protein diffuses on the membrane for around 100 to 380 ms during which time it may cleave about 10 GPI-anchored proteins before dissociating. This combination of short 2-dimensional scoots followed by 3-dimensional hops may be an efficient search strategy on 2-dimensional surfaces with obstacles.