late 13c., from Old English hlaf "portion of bread baked in a mass of definite form," from Proto-Germanic *khlaibuz, the common Germanic word for "bread" (source also of Old Norse hleifr, Swedish lev, Old Frisian hlef, Old High German hleib, German Laib, Gothic hlaifs "bread, loaf").
The Germanic root is of uncertain origin; it is perhaps connected to Old English hlifian "to raise higher, tower," on the notion of the bread rising as it bakes, but (according to OED) it is unclear whether "loaf" or "bread" is the original sense. It is disguised in lord and lady. Finnish leipä, Estonian leip, Old Church Slavonic chlebu, Lithuanian klepas probably are Germanic loan words.
Meaning "chopped meat shaped like a bread loaf" is attested from 1787. Figurative use of loaves and fishes to suggest religious profession for the sake of personal gain" is from John vi.26.