Chemosensory plume-guided navigation, tracking a chemical plume to its source, is a primordial behavior used by many animals to search beyond the visual range. Here we report the first laboratory observations of octopuses performing this behavior, demonstrating that they can use chemosensory plumes to find food. In a three-station discrimination task carried out in the dark, octopus showed a strong preference to move upstream towards the food-baited target, supporting the hypothesis that they are performing chemosensory plume-guided search. When seeking a single baited target, also in the dark, octopuses not only preferred to move upstream towards the food source, but they also displayed characteristic motions associated with odor-gated rheotaxis, a commonly used chemosensory tracking strategy used by many animals, which includes pausing, switchbacks, and across-stream redirections to the bait. Additionally, when approaching single baited stations the octopus often made fast reactive lunging motions. The observation of these fast arm-aligned motions (FAAM), taken together with the observation that the octopus did not have a characteristic body axis orientation to the bait, as would be expected if bilaterally symmetric organs such as the olfactory organs guided this behavior, supports the hypothesis that the suckers are the primary chemosensory organs driving octopus chemosense-guided behaviors.