The queries people issue to a search engine and the results clicked following a query change over time. For example, after the earthquake in Japan in March 2011, the query japan spiked in popularity and people issuing the query were more likely to click government-related results than prior to the earthquake. In this work, we explore the modeling and prediction of such temporal patterns in user search behavior on the Web. We develop a temporal modeling framework adapted from physics and signal processing and harness it to predict temporal patterns in search behavior using smoothing and trends. We explore multiple facets of the dynamics of Web search behavior, including the detection of trends, periodicities, and surprises. Using current and past user behavioral data, we develop a learning procedure that can be used to construct models of users’ Web search activities. Experimental results indicate that our predictive models significantly outperform baseline models that weight historical evidence the same for all queries. We also develop a methodology for learning to identify the best prediction model for a given query or class of queries. Our approach learns to select the best model in an automated manner from a family of predictive models. We present two applications where our temporal modeling of user behavior significantly improves upon the state-of-the-art: time-aware result ranking and time-aware query auto-completion. Finally, we speculate about the use of temporal dynamics to greatly enhance other areas of Web search and information retrieval.