Characterization of vertebrate chemo-orientation strategies over long distances is difficult because it is often not feasible to conduct highly controlled hypothesis-based experiments in natural environments. To overcome the challenge, we couple in-stream behavioral observations of female sea lampreys (Petromyzon marinus) orienting to plumes of a synthesized mating pheromone, 7a,12a,24-trihydroxy-5a-cholan-3-one-24-sulfate (3kPZS), and engineering algorithms to systematically test chemo-orientation hypotheses. In-stream field observations and simulated movements of female sea lampreys according to control algorithms support that odor-conditioned rheotaxis is a component of the mechanism used to track plumes of 3kPZS over hundreds of meters in flowing water. Simulated movements of female sea lampreys do not support that rheotaxis or klinotaxis alone is sufficient to enable the movement patterns displayed by females in locating 3kPZS sources in the experimental stream. Odor-conditioned rheotaxis may not only be effective at small spatial scales as previous described in crustaceans, but may also be effectively used by fishes over hundreds of meters. These results may prove useful for developing management strategies for the control of invasive species that exploit the odor-conditioned tracking behavior and for developing biologically inspired navigation strategies for robotic fish.