<p>Chemotaxis, or the following of chemical concentration gradients, is essential for microbes to locate nutrients. However, microbes often display paradoxical behaviors, such as <i>Escherichia coli</i> being repelled by several amino acids. Here, we explore chemotaxis towards a moving source and demonstrate that when multiple nutrients are released from the source repulsion from certain nutrients actually improves chemotaxis towards the source. Because a moving source leaves most of the nutrient plume behind it, simply following the concentration gradient results in aiming behind the source and potentially failing to intercept it. However, when attraction to a fast-diffusing nutrient and repulsion from a slow-diffusing nutrient are combined, motion in a new direction emerges and the chance of intercepting the source is increased up to six-fold. We demonstrate that this “differential strategy” is robust against numerous variations, including order-of-magnitude increases in the repellent release rate. Finally, we leverage existing data to show that <i>E. coli</i> is attracted to fast-diffusing amino acids and repelled by slow-diffusing ones, suggesting it may utilize a differential strategy and providing an explanation for its repulsion from these amino acids. Our results thus illuminate new possibilities in how microbes can integrate signals from multiple gradients to accomplish challenging chemotactic tasks.</p>