"close friend, roommate, one who shares a bed with another," mid-15c., from bed (n.) + fellow (n.). Also (late 15c) "concubine." Earlier in the "close companion" sense was bed-fere (early 14c.). Old English had simply bedda. Bedsister "husband's concubine" is recorded in Middle English (c. 1300).
Entries linking to bedfellow
Old English bedd "bed, couch, resting place; garden plot," from Proto-Germanic *badja- "sleeping place dug in the ground" (source also of Old Frisian, Old Saxon bed, Middle Dutch bedde, Old Norse beðr, Old High German betti, German Bett, Gothic badi "bed"), sometimes said to be from PIE root *bhedh- "to dig, pierce" (source also of Hittite beda- "to pierce, prick," Greek bothyros "pit," Latin fossa "ditch," Lithuanian bedu, besti "to dig," Breton bez "grave"). But Boutkan doubts this and writes, "there is little reason to assume that the Gmc. peoples (still) lived under such primitive circumstances that they dug out their places to sleep."
Both the sleeping and gardening senses are found in Old English; the specific application to planting is found also in Middle High German and is the only sense of Danish bed. Meaning "bottom of a lake, sea, or watercourse" is from 1580s. Geological sense of "a thick layer, stratum" is from 1680s.
Bed and board "in bed and at the table" (early 13c.) was a term in old law applied to conjugal duties of man and wife; it also could mean "meals and lodging, room and board" (mid-15c.). Bed-and-breakfast in reference to overnight accommodations is from 1838; as a noun, in reference to a place offering such, by 1967.
"companion, comrade," c. 1200, from Old English feolaga "partner, one who shares with another," from Old Norse felagi, from fe "money" (see fee) + lag, from Proto-Germanic *lagam, from PIE root *legh- "to lie down, lay." The etymological sense of fellow seems to be "one who puts down money with another in a joint venture."
Meaning "one of the same kind" is from early 13c.; that of "one of a pair" is from c. 1300. Used familiarly since mid-15c. for "any man, male person," but not etymologically masculine (it is used of women, for example, in Judges xi.37 in the King James version: "And she said unto her father, Let this thing be done for me: let me alone two months, that I may go up and down upon the mountains, and bewail my virginity, I and my fellows").
Its use can be contemptuous or dignified in English and American English, and at different times in its history, depending on who used it to whom, it has carried a tinge of condescension or insult.
University senses (mid-15c., corresponding to Latin socius) evolved from notion of "one of the corporation who constitute a college" and who are paid from its revenues. Fellow well-met "boon companion" is from 1580s, hence hail-fellow-well-met as a figurative phrase for "on intimate terms."
In compounds, with a sense of "co-, joint-," from 16c., and by 19c. also denoting "association with another." Hence fellow-traveler, 1610s in a literal sense but in 20c. with a specific extended sense of "one who sympathizes with the Communist movement but is not a party member" (1936, translating Russian poputchik).
Fellow-countrymen formerly was one of the phrases the British held up to mock the Americans for their ignorance, as it is redundant to say both, until they discovered it dates from the 1580s and was used by Byron and others.