Before this, humanlike creatures - or hominins - ate a forest-based diet similar to modern gorillas and chimps.
Researchers analysed fossilised tooth enamel of 11 species of hominins and other primates found in East Africa.
The findings appear in four papers published in PNAS journal.
Like chimpanzees today, many of our early human ancestors lived in forests and ate a diet of leaves and fruits from trees, shrubs and herbs.
But scientists have now found that this changed 3.5 million years ago in the speciesAustralopithecus afarensis and Kenyanthropus platyops.
Their diet included grasses, sedges, and possibly animals that ate such plants. They also tended to live in the open savannahs of Africa.