BACKGROUND: Brain size is a key adaptive trait. It is often assumed that increasing brain size was a general evolutionary trend in primates, yet recent fossil discoveries have documented brain size decreases in some lineages, raising the question of how general a trend there was for brains to increase in mass over evolutionary time. We present the first systematic phylogenetic analysis designed to answer this question. RESULTS: We performed ancestral state reconstructions of three traits (absolute brain mass, absolute body mass, relative brain mass) using 37 extant and 23 extinct primate species and three approaches to ancestral state reconstruction: parsimony, maximum likelihood and Bayesian Markov-chain Monte Carlo. Both absolute and relative brain mass generally increased over evolutionary time, but body mass did not. Nevertheless both absolute and relative brain mass decreased along several branches. Applying these results to the contentious case of Homo floresiensis, we find a number of scenarios under which the proposed evolution of Homo floresiensis' small brain appears to be consistent with patterns observed along other lineages, dependent on body mass and phylogenetic position. CONCLUSIONS: Our results confirm that brain expansion began early in primate evolution and show that increases occurred in all major clades. Only in terms of an increase in absolute mass does the human lineage appear particularly striking, with both the rate of proportional change in mass and relative brain size having episodes of greater expansion elsewhere on the primate phylogeny. However, decreases in brain mass also occurred along branches in all major clades, and we conclude that, while selection has acted to enlarge primate brains, in some lineages this trend has been reversed. Further analyses of the phylogenetic position of Homo floresiensis and better body mass estimates are required to confirm the plausibility of the evolution of its small brain mass. We find that for our dataset the Bayesian analysis for ancestral state reconstruction is least affected by inclusion of fossil data suggesting that this approach might be preferable for future studies on other taxa with a poor fossil record.