Ecological complexity has been proposed to play a crucial role in primate brain-size evolution. However, detailed quantification of ecological complexity is still limited. Here we assess the spatio-temporal distribution of tropical fruits and young leaves, two primary chimpanzee (Pan troglodytes) foods, focusing on the predictability of their availability in individual trees. Using up to 20 years of information on monthly availability of young leaf, unripe and ripe fruit in plant species consumed by chimpanzees from tropical forests in East, Central, and West Africa, we estimated: (1) the forest-wide frequency of occurrence of each food type and (2) the predictability of finding ripe fruit-bearing trees, focusing on the timing, frequency, and amount of ripe fruit present. In all three forests, at least half of all encountered trees belonged to species that chimpanzees were known to feed on. However, the proportion of these trees bearing young leaves and fruit fluctuated widely between months. Ripe fruit was the most ephemeral food source, and trees that had more than half of their crown filled were at least nine times scarcer than other trees. In old growth forests only one large ripe fruit crop was on average encountered per 10 km. High levels of inter-individual variation in the number of months that fruit was present existed, and in some extreme cases individuals bore ripe fruit more than seven times as often as conspecifics. Some species showed substantially less variation in such ripe fruit production frequencies and fruit quantity than others. We hypothesize that chimpanzees employ a suite of cognitive mechanisms, including abilities to: (1) generalize or classify food trees; (2) remember the relative metrics of quantity and frequency of fruit production across years; and (3) flexibly plan return times to feeding trees to optimize high-energy food consumption in individual trees, and efficient travel between them. Am. J. Primatol. 78:626-645, 2016. © 2016 Wiley Periodicals, Inc.