We study cell navigation in spatiotemporally complex environments by developing a microfluidic racetrack device that creates a traveling wave with multiple peaks and a tunable wave speed. We find that while the population-averaged chemotaxis drift speed increases with wave speed for low wave speed, it decreases sharply for high wave speed. This reversed dependence of population-averaged chemotaxis drift speed on wave speed is caused by a "barrier-crossing" phenomenon, where a cell hops backwards from one peak attractant location to the peak behind by crossing an unfavorable (barrier) region with low attractant concentrations. By using a coarse-grained model of chemotaxis, we map bacterial motility in an attractant field to the random motion of an overdamped particle in an effective potential. The observed barrier-crossing phenomenon of living cells and its dependence on the spatiotemporal profile of attractant concentration are explained quantitatively by Kramers reaction rate theory.