The visual system can learn statistical regularities and form search habits that guide attention to a region where a target frequently appears. Although regularities in the real world can change over time, little is known about how such changes affect habit learning. Using a location probability learning task, we demonstrated that a constant target location probability resulted in a long-term habit-like attentional bias to the target-frequent location. However, when the target probability changed over time in any pattern, the same amount of learning induced only a short-term bias and disrupted the formation of long-term search habits. Moreover, although temporal changes in regularity during initial learning interfered with the acquisition of a search habit, they did not modulate the already consolidated bias. These results suggest that the stability and flexibility of habitual attention learning depend on when and how the statistical regularities in the environment change.