If the tradition of nomadism, horse archery, and generally everything you associate with the Mongols' unprecedented conquest goes back centuries before Genghis, why didn't horse nomads from the steppe terrorize Europe sooner? What was keeping the Scythians or the Xiongnu from (pardon my use of a colloqialism) roflstomping their way through the pre-medieval societies of their times?
Was it just a matter of there being no interest in Westward conquest? Were they too disunified? Or did Genghis' Mongols have some military advantage that the earlier steppe people didn't?
For generations the northern Chinese Jin Dynasty had meddled in Mongol affairs in order to keep them divided and weak because they knew if they ever did unite they would pose a legitimate threat. They forced the clans to give tribute, and if any one clan got too strong, they would do stuff to weaken it like encouraging the Tartars in the north to specifically target the clan with raids. They actually did this during Genghis Khans rise to dominance over the steppes.
A great irony is that at the time of Genghis's rise, the Jin rulers were far less intimidated by the idea of a united Mongolia than their ancestors had been, and sent this message to the Khan at the start of the war between them: "Our Empire is like the sea; yours is but a handful of sand...How can we fear from you?" (Meng Ta Peu Lu Aufzeichnungen über die Mongolischen Tatan von Chao Hung, 1221, p.61)
Of course Genghis and two following Mongol Khans would slowly drain that "sea" dry until it was no more.
Also, ever hear of the Huns? They were a traditionally nomadic people from the steppes of Asia (Scythian territory), and terrorized the pre medieval Europe plenty during their tenure.
Steppe nomads were, in fact, frequently troublesome to the states in the Near East long before Mongol successes.
Spectacularly successful steppe nomads throughout history include the Hephthalites who in the late fifth century defeated the Persian Empire, then the most powerful state in the region jointly with the Eastern Roman Empire. In the 484 Battle of Herat, the Hephtaelites nearly completely wiped out the Persian army, 100,000 strong, and killed the shah, Peroz I. Thereafter, Persia had to pay tribute to the Hepthaelites until their defeat in the early 500s.
A hundred years later, the Avar khaganate reigned supreme over most nomad tribes around the Black Sea. They seem to have had universalist ambitions similar to the Mongols: according to Menander the Guardsman, their envoys to the Byzantine court stated that they were invincible and could easily crush anyone standing in their path. The khaganate was destroyed after the failure of the 626 Avar siege of Constantinople, a major blow to the prestige of the leader of the confederation, the Bayan. (Constantinople, by the way, was a notoriously difficult city to conquer; sieges were quite frequent, but they all failed until the 1204 Sack of Constantinople by crusaders. Off the top of my head, attempts were made by Persia, several by the Rus, Bulgaria, and Arabs).
In the tenth century, nomads were less troublesome to Constantinople itself: Bulgaria acted as a buffer to the West, and Muslim powers as a buffer to the East. Nevertheless, their continuing importance is shown by how preoccupied Byzantine diplomacy could be with nomad powers. A manual on statecraft, De Administrando Imperio, compiled under emperor Constantine VII, focuses heavily on the Pechenegs, a semi-nomadic tribe that the whole world feared. They could be used to deter the tribes around the Black Sea, as well as against settled powers such as Bulgaria. In the same period, Magyars were a frequent source of trouble to the German emperors until their decisive defeat in Lechfeld, 955.
So, powerful nomad tribes penetrating deep into Europe were nothing new. Many before the Mongols had universalist ambitions and similarly believed that they could conquer the whole world. I would say, however, that there were two main differences:
The world of Eastern Europe, even in the tenth century, was relatively fluid and full of nomadic tribes. As tribes displaced each other in the Black Sea and to the East, there was frequently an influx of new tribes into Europe that would defeat the existing inhabitants, causing fresh migrations. This is less clear in the historical record than the terror of the thirteenth century inhabitants of states such as Hungaria. So - the nomads' movements were broadly similar, but the populations they attacked were now different; settled, a part of the broader Latin Christendom, and thus more likely to leave records of their terror and through this to inspire fear in the rest of Europe.
The Mongols were no doubt an especially large and well organised confederation of tribes, but the situation in the Near East was also rather different than even a hundred years earlier. Though the Abbasid Caliphate had experienced a military revival, the other states in the area were not faring very well. Persia had obviously collapsed in the Arab conquests in the late seventh century, thus leaving the Byzantine Empire. Previously a master of manipulating steppe nomads and pitting them up against each other, the empire had been in decline for a long period of time, and the Sack of Constantinople in 1204 had been a heavy blow to its power and, perhaps especially importantly, its prestige.
One thing in particular I would like to add is that Genghis was the first of his kind to promote and reward people based on merit rather than social hierarchy, so it created not only loyalty to Kahn, but also created a better standing army.