Recently, it has been proposed that the one of the main determinants of complex societies in Hymenoptera is colony size, since the existence of large colonies reduces the direct reproductive success of an average individual, given a decreased chance of being part of the reproductive caste. In this study, we evaluate colony size evolution in corbiculate bees and their relationship with the sociality level shown by these bees. Specifically i) the correlation between colony size and level of sociality considering the phylogenetic relationship to evaluate a general evolutionary tendency, and ii) the hypothetical ancestral forms of several clades within a phylogeny of corbiculate bees, to address idiosyncratic process occurring at important nodes. We found that the level of social complexity in corbiculate bees is phylogenetically correlated with colony size. Additionally, another process is invoked to propose why colony size evolved concurrently with the level of social complexity. The study of this trait improves the understanding of the evolutionary transition from simple to complex societies, and highlights the importance of explicit probabilistic models to test the evolution of other important characters involved in the origin of eusociality.