Natural killer (NK) cells play a central role during innate immune responses by eliminating pathogen-infected or tumorigenic cells. In the microenvironment, NK cells encounter not only target cells but also other cell types including non-target bystander cells. The impact of bystander cells on NK killing efficiency is, however, still elusive. In this study we show that the presence of bystander cells, such as P815, monocytes or HUVEC, enhances NK killing efficiency. With bystander cells present, the velocity and persistence of NK cells were increased, whereas the degranulation of lytic granules remained unchanged. Bystander cell-derived H2O2 was found to mediate the acceleration of NK cell migration. Using mathematical diffusion models, we confirm that local acceleration of NK cells in the vicinity of bystander cells reduces their search time to locate target cells. In addition, we found that integrin β chains (β1, β2 and β7) on NK cells are required for bystander-enhanced NK migration persistence. In conclusion, we show that acceleration of NK cell migration in the vicinity of H2O2-producing bystander cells reduces target cell search time and enhances NK killing efficiency.