Une des principales raisons expliquant la large diffusion de l’espèce est que le Babouin olive n'est pas dépendant d'une source de nourriture unique. Il est omnivore, trouvant son alimentation dans n’importe quel environnement et capable de s’adapter à différentes stratégies pour trouver sa nourriture. Par exemple, un babouin olive vivant dans la steppe se nourrira différemment d’un autre vivant dans la forêt. Il est aussi intéressant de noter que le babouin utilise l’intégralité de son environnement pour se nourrir : sur et sous le sol ou dans la canopée, alors que la plupart des animaux ne cherchent leur nourriture qu'à un seul niveau.
Ainsi, une espèce arboricole comme le lémurien ne cherche jamais sa nourriture au sol. Le babouin olive cherchera dans toutes les zones possibles et mangera presque tout ce qu’il trouvera. Cela inclut une grande variété de plantes, d’invertébrés et de petits vertébrés. Le babouin olive mange feuilles, herbe, racines, écorce, fleur, fruit, lichens, tubercules, graines, champignons, cormes et rhizomes. Les cormes et les rhizomes sont particulièrement importants en période de sécheresse, l’herbe perdant une grande partie de sa valeur nutritionnelle. Dans les régions arides, tels que les déserts du nord-est de l’Afrique, les petits invertébrés comme les insectes, les araignées et les scorpions constituent son alimentation.
Le babouin olive est aussi adepte de la chasse, s’alimentant de petits rongeurs et lapins mais également d’autres mammifères et d’autres primates. Sa limite est généralement les petits cervidés tels que la gazelle de Thomson qui représente 33% de la nourriture issue de sa chasse. Il s’agit généralement d’une activité de groupe à laquelle participent indistinctement mâles et femelles.Il est intéressant de noter qu'il y a des preuves que ce comportement a été développé récemment. Dans une étude de terrain, un tel comportement a été observé comme commençant avec les mâles d’une troupe se répand pour impliquer les singes de tout âges et tout sexes.