mid-12c., "large group of people," from Old French compagnie "society, friendship, intimacy; body of soldiers" (12c.), from Late Latin companio, literally "bread fellow, messmate," from Latin com "with, together" (see com-) + panis "bread," from PIE root *pa- "to feed." Abbreviation co. dates from 1670s.
Meaning "companionship, consort of persons one with another, intimate association" is from late 13c. Meaning "person or persons associated with another in any way" is from c. 1300. In Middle English the word also could mean "sexual union, intercourse" (c. 1300).
From late 14c. as "a number of persons united to perform or carry out anything jointly," which developed a commercial sense of "business association" by 1550s, the word having been used in reference to trade guilds from late 14c. Meaning "subdivision of an infantry regiment" (in 19c. usually 60 to 100 men, commanded by a captain) is from c. 1400.
Meaning "person or persons with whom one voluntarily associates" is from c. 1600; phrase keep company "consort" is from 1560s (bear company in the same sense is from c. 1300). Expression two's company "two persons are just right" (for conversation, etc.), is attested from 1849; the following line varies: but three is none (or not), 1849; three's trumpery (1864); three's a crowd (1856).