The present study attempted to reconstruct 3D brain shape of Neanderthals and early Homo sapiens based on computational neuroanatomy. We found that early Homo sapiens had relatively larger cerebellar hemispheres but a smaller occipital region in the cerebrum than Neanderthals long before the time that Neanderthals disappeared. Further, using behavioural and structural imaging data of living humans, the abilities such as cognitive flexibility, attention, the language processing, episodic and working memory capacity were positively correlated with size-adjusted cerebellar volume. As the cerebellar hemispheres are structured as a large array of uniform neural modules, a larger cerebellum may possess a larger capacity for cognitive information processing. Such a neuroanatomical difference in the cerebellum may have caused important differences in cognitive and social abilities between the two species and might have contributed to the replacement of Neanderthals by early Homo sapiens.