As the largest and among the most behaviourally complex extant terrestrial mammals, proboscideans (elephants and their extinct relatives) are iconic representatives of the modern megafauna. The timing of the evolution of large brain size and above average encephalization quotient remains poorly understood due to the paucity of described endocranial casts. Here we created the most complete dataset on proboscidean endocranial capacity and analysed it using phylogenetic comparative methods and ancestral character states reconstruction using maximum likelihood. Our analyses support that, in general, brain size and body mass co-evolved in proboscideans across the Cenozoic; however, this pattern appears disrupted by two instances of specific increases in relative brain size in the late Oligocene and early Miocene. These increases in encephalization quotients seem to correspond to intervals of important climatic, environmental and faunal changes in Africa that may have positively selected for larger brain size or body mass.