c. 1200, feolahschipe "companionship," from fellow + -ship. Sense of "a body of companions" is from late 13c. Meaning "spirit of comradeship, friendliness" is from late 14c. As a state of privilege in English colleges, from 1530s. In Middle English it was at times a euphemism for "sexual intercourse" (carnal fellowship).
To fellowship with is to hold communion with; to unite with in doctrine and discipline. This barbarism now appears with disgusting frequency in the reports of ecclesiastical conventions, and in the religious newspapers generally. [Bartlett, "Dictionary of Americanisms," 1848]
But Chaucer and Wyclif used it as a verb in Middle English, "to have fellowship with."