Europe was a pretty big place in the Middle Ages; but to put it simply, and I can only speak for the British Isles, there was always a "national" monarchy in some form or another. The Anglo-Saxon Chronicle and Bede name a number of Northumbrian kings as Bretwalda, meaning that they were considered to essentially be the Emperors of the Anglo-Saxons.
Cnut the Great, a Viking who conquered England and became its king, didn't have much of a cultural impact and has come to be regarded as something of an Anglo-Saxon convert. The only really big societal shift came with the Norman Conquest. That should be recent enough that it need not be rehashed outside of high school English.
So, in essence, from the fall of the Roman Empire to the Norman Conquest, there was (in theory) an absolute ruler with powers above that of his fellow kings in Britain.
If you're asking how our contemporary European nation-states came to be, then a better suited question would be how the end of the Viking incursions into Europe allowed for political and social settlement.