Middle English, representing the merger or mutual influence of two words, one from Old English, one from an Old French form of the same Germanic word, and both ultimately from a PIE root meaning "cattle."
The Old English word is feoh "livestock, cattle; movable property; possessions in livestock, goods, or money; riches, treasure, wealth; money as a medium of exchange or payment," from Proto-Germanic *fehu (source also of Old Saxon fehu, Old High German fihu, German Vieh "cattle," Gothic faihu "money, fortune"). This is from PIE *peku- "cattle" (source also of Sanskrit pasu, Lithuanian pekus "cattle;" Latin pecu "cattle," pecunia "money, property").
The other word is Anglo-French fee, from Old French fieu, a variant of fief "possession, holding, domain; feudal duties, payment" (see fief), which apparently is a Germanic compound in which the first element is cognate with Old English feoh.
Via Anglo-French come the legal senses "estate in land or tenements held on condition of feudal homage; land, property, possession" (c. 1300). Hence fee-simple (late 14c.) "absolute ownership," as opposed to fee-tail (early 15c.) "entailed ownership," inheritance limited to some particular class of heirs (second element from Old French taillir "to cut, to limit").
The feudal sense was extended from landholdings to inheritable offices of service to a feudal lord (late 14c.; in Anglo-French late 13c.), for example forester of fe "a forester by heritable right." As these often were offices of profit, the word came to be used for "remuneration for service in office" (late 14c.), hence, "payment for (any kind of) work or services" (late 14c.). From late 14c. as "a sum paid for a privilege" (originally admission to a guild); early 15c. as "money payment or charge exacted for a licence, etc."