In ancient Rome a "benefice" (from the Latin noun beneficium, meaning "benefit") was a gift of land (precaria) for life as a reward for services rendered, originally, to the state. In medieval Latin European documents, a land grant in exchange for service continued to be called a beneficium (Latin). Later, the term feudum, or feodum, began to replace beneficium in the documents. The first attested instance of this is from 984, although more primitive forms were seen up to one hundred years earlier. The origin of the feudum and why it replaced beneficium has not been well established, but there are multiple theories, described below.
The most widely held theory is put forth by Marc Bloch that it is related to the Frankish term *fehu-ôd, in which *fehu means "cattle" and -ôd means "goods", implying "a moveable object of value." When land replaced currency as the primary store of value, the Germanic word *fehu-ôd replaced the Latin word beneficium. This Germanic origin theory was also shared by William Stubbs in the nineteenth century.
A theory put forward by Archibald R. Lewis that the origin of 'fief' is not feudum (or feodum), but rather foderum, the earliest attested use being in Astronomus's Vita Hludovici (840). In that text is a passage about Louis the Pious which says annona militaris quas vulgo foderum vocant, which can be translated as "(Louis forbade that) military provender which they popularly call 'fodder' (be furnished)."
A theory by Alauddin Samarrai suggests an Arabic origin, from fuyū (the plural of fay, which literally means "the returned", and was used especially for 'land that has been conquered from enemies that did not fight'). Samarrai's theory is that early forms of 'fief' include feo, feu, feuz, feuum and others, the plurality of forms strongly suggesting origins from a loanword. First use of these terms was in Languedoc, one of the least-Germanized areas of Europe and bordered Muslim Spain, where the earliest use of feuum as a replacement for beneficium can be dated to 899, the same year a Muslim base at Fraxinetum (La Garde-Freinet) in Provence was established. It is possible, Samarrai says, that French scribes, writing in Latin, attempted to transliterate the Arabic word fuyū (the plural of fay), which was being used by the Muslim invaders and occupiers at the time, resulting in a plurality of forms - feo, feu, feuz, feuum and others - from which eventually feudum derived. Samarrai, however, also advises medieval and early modern Muslim scribes often used etymologically "fanciful roots" in order to claim the most outlandish things to be of Arabian or Muslim origin.
In the 10th and 11th centuries the Latin terms for fee could be used either to describe dependent tenure held by a man from his lord, as the term is used now by historians, or it could mean simply "property" (the manor was, in effect, a small fief). It lacked a precise meaning until the middle of the 12th century, when it received formal definition from land lawyers.
In English usage, the word "fee" is first attested around 1250–1300 (Middle English); the word fief from around 1605–15. In French, the term fief is found from the middle of the 13th century (Old French), derived from the 11th-century terms feu, fie. The odd appearance of the second f in the form fief may be due to influence from the verb fiever 'to grant in fee'. In French, one also finds "seigneurie" (land and rights possessed by a "seigneur" or "lord", 12th-century), which gives rise to the expression "seigneurial system" to describe feudalism.
Originally, vassalage did not imply the giving or receiving of landholdings (which were granted only as a reward for loyalty), but by the eighth century the giving of a landholding was becoming standard. The granting of a landholding to a vassal did not relinquish the lord's property rights, but only the use of the lands and their income; the granting lord retained ultimate ownership of the fee and could, technically, recover the lands in case of disloyalty or death. In 8th-century France, Charles Martel was the first to make large-scale and systematic use (the practice had remained until then sporadic) of the remuneration of vassals by the concession of the usufruct of lands (a beneficatium or "benefice" in the documents) for the life of the vassal, or, sometimes extending to the second or third generation.