Standard consumer search models typically assume a stationary environment in which past experiences do not influence current search effectiveness. Leveraging unique data on individual-level repeated refueling transactions and variations in market familiarity, this paper instead documents that search behavior is strongly experience-dependent. When drivers refuel in unfamiliar markets, due to travel or residential relocation, they pay prices that are around 1 % (equivalent to around 0.3 standard deviations) higher than in familiar markets. This experience premium persists, but decreases with accumulating experience. Our decomposition analysis suggests that these effects are primarily driven by learning about the store and the market.