Exactly, Stone Age man had to hunt his food and that meant hiking/hunting all day long until you found some game. And then there were days where you had to go a day or a few without eating anything other than some berries.
A priori that story seems right. But surely early man still had to survive Winter, so they actually would have had techniques to store and preserve foods (smoking, drying) and so would likely have picked a pile of berries/nuts and carried them to ration over the time spent hunting, or kept dried meat to hand? For sure you'd also have days where you'd eaten all the food, just as people do now.