Females can maximize the benefits of mate choice by finding high-quality mates while using search tactics that limit the costs of searching for mates. Mate-searching models indicate that specific search tactics would best optimize this trade-off under different conditions. These models do not, however, consider that females may use information from previous years to improve mate searching and reduce search costs in subsequent years. We followed female satin bowerbirds Ptilonorhynchus violaceus during mate searching and reconstructed their search patterns. We found that females who chose very attractive males typically mated with the same male in the following year, resulting in these females sampling fewer males than those who switched mates. In contrast, females who mated with less attractive males typically rejected their previous mates and searched longer for more attractive mates in the following mating season. A potential cost to mate searching is suggested by the observed increase in the likelihood of force-copulation attempts from marauding males with increased searching. Our results suggest that by using past experiences to adjust their search tactics, females may obtain high-quality mates while limiting search costs. These results emphasize the need to consider historical effects in studies of sexual selection, especially for long-lived species with stable display sites.