Feudalism had its origin in Roman and early Germanic practices. The Romans employed methods of land tenure other than simple ownership. Precariumwas a land grant by a landowner to someone who offered service in return for protection. Beneficiumwas precarium for a fixed time, often for life. Vassalage, the holding of another's land in return for homage and fealty, and immunity, a powerful individual's exemption from the king's jurisdiction, also existed. Commendationwas a practice among Germanic warriors of voluntarily surrendering land and freedom to a more powerful warrior in return for protection.

The absence of any lasting, central authority after the decline of the western Roman Empire in the fifth century required many individuals to make personal arrangements for their safety. The need for such arrangements became acute because of raids during the 5th through the 11th centuries by Germanic tribes, Vikings, and Saracens. The chaos created by the raids helped the practices of precarium, vassalage, immunity, and commendation to evolve into feudalism.

Feudalism first took definite form in France during the 9th and 10th centuries. Wealthy landowners and warriors built castles to protect themselves and their followers. Beneficia became hereditary fiefs as kings were no longer powerful enough to reclaim land grants. Nobles also proclaimed rights of seignorial jurisdiction and immunity from royal authority.

Anglo-Saxon England was not a feudal society, although large landowners, called earls, had extensive powers. William the Conqueror introduced feudalism in 1066, but maintained royal authority by requiring all intermediate and lesser vassals to swear fealty directly to him. Important vassals were given scattered tracts of land to keep them from controlling a region.

Otto I (reigned 936–73) strengthened the German throne at the expense of the nobles, and in 962 he was crowned first Holy Roman Emperor. However, several factors weakened royal power: the elective nature of the German throne, the involvement of German kings in Italian affairs, and the ongoing struggle between various emperors and popes. The end of the Hohenstaufen dynasty in 1254 ended prospects for strong royal rule, and German feudalism endured for centuries.

The early revival of trade in northern Italy created a league of city-states that became virtually independent of both royal and feudal authority. Southern Italy and Sicily were conquered by the Normans in the 11th century and became a feudal kingdom.

Feudalism was introduced by conquest into Palestine by the Crusaders, and into the Baltic lands by the Teutonic Knights. The Scandinavian nations adopted certain feudal customs but remained largely non-feudal.

During the early Middle Ages, the church was in disarray because of political disorder in Europe. Powerful nobles seized church lands and divided them into fiefs for their supporters. Many of these nobles claimed the right of investing high church officials with the symbols of office, in effect becoming their overlords. Attempts by the church to end this practice led to the Investiture Controversy (1075–1122). The controversy ended in a compromise and the church regained some authority.