In addition, another class of cell-cell communication is by long, thin cellular protrusions that are ~100 microns (many cell-lengths) in length and ~100 nanometers (below traditional microscope resolution) in width. These protrusions have been recently discovered in many organisms, including nanotubes humans and airinemes in zebrafish. But, before establishing communication, these protrusions must find their target cell. Here we demonstrate airinemes in zebrafish are consistent with a finite persistent random walk model. We study this model by stochastic simulation, and by numerically solving the survival probability equation using Strang splitting. The probability of contacting the target cell is maximized for a balance between ballistic search (straight) and diffusive (highly curved, random) search. We find that the curvature of airinemes in zebrafish, extracted from live cell microscopy, is approximately the same value as the optimum in the simple persistent random walk model. We also explore the ability of the target cell to infer direction of the airineme’s source, finding the experimentally observed parameters to be at a Pareto optimum balancing directional sensing with contact initiation.