The so-called “paradox of voting” is major anomaly for rational choice theories of elections. If voting is costly and citizens are rational then large electorates the expected turnout would be small, for if many people voted the chance of anyone being pivotal would be too small to make the act worthwhile. Yet many people do vote, even in large national elections. To address this puzzle we construct a model of adaptive rationality: citizens learn by simple trial-and-error, repeating satisfactory actions and avoiding unsatisfactory ones. (Their aspiration levels, which code current payoffs as satisfactory or unsatisfactory, are also endogenous, themselves adjusting to experience.) Our main result is that agents who adapt in this manner turn out in substantial numbers even in large electorates and even if voting is costly for everyone.