We show that customer loyalty programs, and more specifically, discounts for frequent buyers, are an outcome of price discrimination by firms in imperfectly competitive markets with costly consumer search. We consider models of both search goods and experience goods when consumers differ only in their purchase frequency. Consumers’ valuations are drawn from the same distribution and consumers have identical costs of search. However, because frequent buyers have greater incentives to search, in equilibrium they have better outside options, search more often, and have higher ex post expected valuations. Competing firms offer lower prices to frequent buyers, and when consumers’ purchase frequency is private information, they do so using loyalty programs or frequent buyer discounts. These consumers receive lower prices even though in equilibrium they have greater gains from trade (higher valuations).