Chemotaxis allows bacteria to follow gradients of nutrients and other environmental stimuli. The bacterium Escherichia coli performs chemotaxis via a run-and-tumble strategy in which sensitive temporal comparisons lead to a biased random walk, with longer runs in the preferred gradient direction. The chemotaxis network of E. coli has developed over the years into one of the most thoroughly studied model systems for signal transduction and behavior, yielding general insights into such properties of cellular networks as signal amplification, signal integration, and robustness. Despite its relative simplicity, the operation of the E. coli chemotaxis network is highly refined and evolutionarily optimized at many levels. For example, recent studies revealed that the network adjusts its signaling properties dependent on the extracellular environment, apparently to optimize chemotaxis under particular conditions. The network can even utilize potentially detrimental stochastic fluctuations in protein levels and reaction rates to maximize the chemotactic performance of the population.