Of course, that was the basis of all the system.
All nobles were, ultimately, vassals of the King, since in theory, all the kingdom was a property of the King. Intermediate levels of vassalage existed, so that a count could pay homage to the King directly, or to a duke. Lower noblity, castillians and other men in charge of small bands and infrastructures usually paid homage to their direct lord (in practice, the King had no real power over these men). Some very low ranking nobles could be vassals of a lord with no fief in exchange.
It is important to understand the key factor here: that a noble paid homage in exchange of a territory (a fief). This resulted in combulated situations. Let me put two examples:
First. A noble could be vassal of a King, but just in a certain territory. The count of Normandy was a vassal of the King of French because of Normandy; however, when one of them conquered England and became king (William the Conqueror), the Kingdom of England was not subjected to the King of France. The King of England was vassal of the King of France not because of England, but just because he was count of Normandy, an integral part of the Kingdom of France (and then, Anjou, Aquitaine or other territories).
Second: A noble could be vassal of two lords. Charles the Bold was vassal of the King of France because of the County of Burgundy (and other territories), and vassal of the Emperor because of the Duchy of Luxemburg (and other territories)
In the late Middle Ages, lot of petty nobility became lordless (although, as I said, ultimately they had a king). They filled the ranks of mercenary bands that served the kings of France, England, Castile, Aragon, in Italy, Germany etc If defeated or in trouble, or during peace time, they went into banditry in all of Europe, causing lot of troubles (and myths). When the royal armies were developed by the mid and late 15th century, these petty nobles filled their ranks (as men-at-arms, swordmen, pikemen etc), with increasing presence of plebeians, mostly from the cities (armed with polearms and crossbows, then with handguns, increasingly adopted by nobles). The longbowmen of England were in a intermediate level: they were usually yeomen, a social class on the fringe of nobility and peasantry
Curiously, a similar situation developed in Japan with the ashigarus, ronin etc