c. 1300, "one who accompanies or associates with another," from Old French compagnon "fellow, mate, friend, partner" (12c.), from Late Latin companionem (nominative companio), literally "bread fellow, messmate," from Latin com "with, together" (see com-) + panis "bread," from PIE root *pa- "to feed."
The Late Latin word is found first in the 6c. Frankish Lex Salica, and probably it is a translation of some Germanic word (compare Gothic gahlaiba "messmate," from hlaib "loaf of bread"). It replaced Old English gefera "traveling companion," from faran "go, fare."
The meaning "A person who lives with another in need of society, and who, though receiving remuneration, is treated rather as a friend and equal than as an inferior or servant" [OED] is from 1766.