As you say, it wouldn’t make much sense to first domesticate cereals and then discover how to eat them, in the form of bread or otherwise. Fortunately, this is not how it happened. Humans were eating cereals and making “bread” long before we ever domesticated any cereal.

Cereal domestication began with barley, emmer and einkorn wheat in the middle east, around 10,000 years ago. But humans were gathering grains from the wild forms of these plants long before that. For example, we have 23,000 year old archaeological remains at the Ohalo II site in Israel, showing that humans were processing cereals (barley and wheat) by pounding them with stones to produce flour, and baking some kind of bread in an oven-like hearth.

• Piperno, D. R., Weiss, E., Holst, I. & Nadel, D. Processing of wild cereal grains in the Upper Palaeolithic revealed by starch grain analysis. Nature 430, 670–673 (2004).

Grains are extremely rich sources of protein, and dense packed seeds from grasses like barley or early wheat were important to our hunting/gathering ancestors. Long before domestication, they were gathering cereals and other plant products. It’s true that cereals are kind of hard and tough to eat without processing and cooking, but fortunately, these things also have a long history predating domestication.

For example, we have evidence of extensive plant food processing at various sites in Italy, Russia and the Czech Republic, dating from 30,000 years or even earlier. At these sites, humans were gathering tough plant materials including roots, rhizomes, and even some seeds, and were then grinding and cooking them to make them easier to eat and to increase their caloric value.

• Revedin, A. et al. Thirty thousand-year-old evidence of plant food processing. Proc. Natl. Acad. Sci. U. S. A. 107, 18815–18819 (2010).

In fact, processing and cooking plant foods isn’t just restricted to our species, we have evidence of Neanderthals at Shanidar Cave in Iran and Spy Cave in Belgium cooking several plant foods, including seeds:

• Henry, A. G., Brooks, A. S. & Piperno, D. R. Microfossils in calculus demonstrate consumption of plants and cooked foods in Neanderthal diets (Shanidar III, Iraq; Spy I and II, Belgium). PNAS 108, 486–491 (2011).

So the likely scenario is that very long ago before domestication and agriculture, our ancestors gathered plant foods, including foods that are good sources of nutrients but are too tough to chew. These foods were then processed, mostly by pounding to create a paste if wet, or a flour if dry, and were then cooked before eating.

A very simple way to cook flour is to mix it with a bit of water and spread the paste on a stone which you put by the fire. This produces a simple flatbread, which is the earliest form of bread. Ovens produce a more even heating compared to an open fire, and we have evidence of oven-like enclosures associated with hearths by at least 20,000 years ago.

Leavening bread so that it will rise is a much later invention, and did not become routine practice until after agriculture, probably around 6,000 - 7,000 years ago.