They definitely ate fruit. Last year, paleoanthropologists found bits of date stuck in the teeth of a 40,000-year-old Neanderthal. There's evidence that several of the fruits we enjoy eating today have been around for millennia in much the same form. For example, archaeologists have uncovered evidence of 780,000-year-old figs at a site in Northern Israel, as well as olives, plums, and pears from the paleolithic era. Researchers have also dug up grapes that appear to be 7 million years old in northeastern Tennessee (although, oddly, the grapes are morphologically more similar to today’s Asian varieties than the modern grapes considered native to North America). Apple trees blanketed Kazakhstan 30,000 years ago, oranges were common in China, and wild berries grew in Europe. None of these fruits were identical to the modern varieties, but they would have been perfectly edible.
It’s not altogether clear why fruits have changed less than vegetables, but it might have something to do with their evolutionary purpose. Plants developed sugary fruits millions of years ago so that sweet-toothed mammals would gobble them up and disseminate the seeds. By the time hominids descended from the African tree canopy, delicious fruits were widely available with no need for artificial selection. Since vegetables gain nothing from being eaten, they didn't experience the same pressure to evolve delectable roots, stems, and leaves.Vegetables are a different story. Many of the ones we eat today have undergone profound changes at the hands of human farmers. Consider the brassicas: Between8,000 and 10,000 years ago, humans took a leafy green plant and, by selecting for different characteristics, began to transform it into several different products. Modern kale, cabbage, broccoli, cauliflower, Brussels sprouts, and kohlrabi are all members of the same species, derived from a single prehistoric plant variety. Wild carrots may predate human agriculture, but they’re unpalatable and look nothing like the cultivated variety. The earliest domesticated carrots were probably purple, and the orange carrot emerged in the 17th century. While legumes predate the dawn of man, modern green beans are a human invention.
Just because there are some paleolithic fruits in production today doesn’t mean you can easily mimic the paleolithic diet. Modern apples, dates, figs, and pears aren’t necessarily nutritionally equivalent to their late Stone Age ancestors. Selection by humans has made them larger and sweeter, and may have caused other chemical changes. Ancient man also ate plants that you can’t find at a grocery store, like ferns and cattails. His relative dietary proportions of meats, nuts, fruits, and vegetables are in dispute, and probably varied significantly with location. Some paleoanthropologists also believe hunter-gatherers ate a far wider variety of foods than modern man, each in a smaller quantity, to minimize the risk of poisoning.