We present an algorithm for underwater robots to track mobile targets, and specifically human divers, by detecting periodic motion. Periodic motion is typically associated with propulsion underwater and specifically with the kicking of human swimmers. By computing local amplitude spectra in a video sequence, we find the location of a diver in the robot's field of view. We use the Fourier transform to extract the responses of varying intensities in the image space over time to detect characteristic low frequency oscillations to identify an undulating flipper motion associated with typical gaits. In case of detecting multiple locations that exhibit large low-frequency energy responses, we combine the gait detector with other methods to eliminate false detections. We present results of our algorithm on open-ocean video footage of swimming divers, and also discuss possible extensions and enhancements of the proposed approach for tracking other objects that exhibit low-frequency oscillatory motion.