Neutrophils and monocytes are sentinels of inflammatory signals. To reach the sites of action, both cell types attach to and then transmigrate the endothelial cell layer that lines the luminal side of blood vessels. While it has been reported that neutrophils and monocytes actively migrate along the surface of the vasculature, it remains elusive whether and how these motion patterns augment the efficiency of the immune system. Here, we conducted co-culture experiments of primary human monocytes and neutrophils, respectively, with primary human umbilical vein endothelial cells (HUVECs). Combining classical biomedical approaches with quantitative image analysis and numerical models, we find that immune cells simultaneously increase the number of sampled cells versus traveled distance and sensitivity to chemokines by migrating along endothelial cell-cell boundaries. Collectively, these findings establish search optimization of neutrophils and monocytes through limitation of motion pattern to cell-cell boundaries.