Sexually reproducing organisms require males and females to find each other. Increased difficulty of females finding mates as male density declines is the most frequently reported mechanism of Allee effects in animals. Evolving more effective mate search may alleviate Allee effects, but may depend on density regimes a population experiences. In particular, high-density populations may evolve mechanisms that induce Allee effects which become detrimental when populations are reduced and maintained at a low density. We develop an individual-based, eco-genetic model to study how mating systems and fitness trade-offs interact with changes in population density to drive evolution of the rate at which males or females search for mates. Finite mate search rate triggers Allee effects in our model and we explore how these Allee effects respond to such evolution. We allow a population to adapt to several population density regimes and examine whether high-density populations are likely to reverse adaptations attained at low densities. We find density-dependent selection in most of scenarios, leading to search rates that result in lower Allee thresholds in populations kept at lower densities. This mainly occurs when fecundity costs are imposed on mate search, and provides an explanation for why Allee effects are often observed in anthropogenically rare species. Optimizing selection, where the attained trait value minimizes the Allee threshold independent of population density, depended on the trade-off between search and survival, combined with monogamy when females were searching. Other scenarios led to runaway selection on the mate search rate, including evolutionary suicide. Trade-offs involved in mate search may thus be crucial to determining how density influences the evolution of Allee effects. Previous studies did not examine evolution of a trait related to the strength of Allee effects under density variation. We emphasize the crucial role that mating systems, fitness trade-offs and the evolving sex have in determining the density threshold for population persistence, in particular since evolution need not always take the Allee threshold to its minimum value.