Mate-choice studies typically focus on male traits affecting female mating decisions, but few studies seek to identify the behavioral rules females use when searching for mates. Current models suggest that females may either directly compare a set of males (‘pooled comparison’) or compare each male to an internal standard (‘sequential-search rule’) when judging the suitability of potential mates. Models also differ in other specific aspects, such as the predicted number of sampling bouts initiated and the tendency of females to return to males after previous visits. We monitored 63 female satin bowerbirds, Ptilonorhynchus violaceus, during mate sampling to reconstruct their search patterns. We found that females typically sampled several mates and returned to the most attractive male for mating: a behavior consistent with the pooled-comparison tactic. Females, however, varied in the number of males sampled; some visited only one male before mating. We found that this variation can be explained by differences among females in the number of mates, the date mate searching is initiated, and long-term experience with males. Further, females were observed to initiate two distinct sampling bouts, with the rejection of most of their potential mates occurring before the start of the second sampling bout. This suggests that the choices of potential mates are narrowed prior to the second sampling bout and that the later visits may function to reconsider preliminary decisions made during the first sampling bout or to resolve decisions concerning the remaining potential mates. Our results indicate that mate searching is a complex process in which females use multiple sampling bouts to find suitable mates and in which several different factors influence their search behavior.