Allegiance doesn't reliably jump about magically in the real world the way it seems like it would by succession law and the like. Plus, you're overlooking the fact that the two-sentence version of how Rome actually fell would have it falling to those very Germanic tribes who nominally followed it.

It's more accurate to say that in the Germanic-controlled parts of Europe, a sort of feudal system already prevailed, with people owing allegiance to local lords who owed it to ceremonial kings, many of whom swore oaths to Rome and became part of its empire. As the power of that empire waned, the kings derived legitimacy through local succession rather than through the once-mighty empire, though they still also paid lip service to the notion that they were Imperial subjects. After the fall of the city of Rome, the title of Roman Emperor (in the west) continued for a little while, with different Germanic tribes fighting for it, but in time it stopped being relevant at all. The same proto-feudalism continued, without any empire or any relevant rank higher than that of king.

In the Mediterranean, the Eastern Roman Empire then started doing a pretty good job of retaking a lot of the former empire to the west, including most of Italy, before being undone by the Plague of Justinian in the mid 6th century. What was left of their westward expansion was governed out of Ravenna, but still included the city of Rome.

Fast-forward from there about 150 years. Arguably, the Holy Roman Empire was established in the 720s, it just didn't have that name yet. That's approximately when Charles Martel unified the "Stem Duchies" under one king (Theuderic IV) to rule both the historical Frankish kingdoms of Austrasia and Neustria along with Bavaria, Alemannia, and Saxony, as well as bringing Aquitaine and Burgundy under nominal Frankish rule.

Note that the kings' hold on these possessions as ceremonial rulers to whom the locals pay homage is pretty solid, but by Martel's day the Frankish kings had almost no real-world power, which rested instead with the Mayors of the Palace, a hereditary title that had originally meant something like "prime minister" but turned into "dictator, and king in all but name." (Charles Martel was, himself, Mayor of the Palace; the dynasty he founded is known as the Carolingians.) When Theuderic died, Martel didn't even bother propping up a new king, and the Franks went through a brief interregnum.

Charles was succeeded by his two sons, Pippin the Short as Mayor of the Palace of Neustria and Carloman as Mayor of the Palace of Austrasia, who together propped up King Childeric III. Childeric's ceremonial realm included both Neustria and Austrasia, but that's kind of like how Queen Elizabeth is the head of state in both Canada and Australia. The two were also political rivals, and Pippin deposed Carloman, sending him to a monastery while Pippin assumed the reins of power throughout the Frankish realm, also bringing the Dukes under a little bit more of his control than previously.

Meanwhile, the Lombards had conquered Ravenna and toppled Byzantine Italy, and were marching on Rome. The Pope called upon the Franks for aid. While they were working on this problem, Pippin sent Pope Zachary a letter asking him whether it is proper for the King of the Franks to have the royal title but not the power that should go along with it; Zachary took the hint, answered that it is unnatural and improper, and once Pippin's armies dealt with the threat to Rome, he crowned Pippin the King of the Franks. Pippin thanked him with the Donation of Pippin, which is where he more or less conquered Rome himself and gave it and the surrounding lands to the papacy. (This would later become the Papal States, which you'll hear about a lot in medieval and early modern Italian studies.) This broke the Papacy's dependence on the Emperor, who formerly had the right to confirm or reject anyone elected to the office of Pope.

Asserting this authority by giving Pippin a crown also enhanced Zachary's own legitimacy as an independent power, both because it meant that he was no longer an Imperial puppet and because it showed that despite Pippin having given him his land, even Pippin would kneel before him for a crown. Mostly, though, the authority to do it came from the fact that Pippin needed it to be there so he could depose Childeric, and the Carolingian empire was the superpower of western Europe at the time; the Pope power over the Frankish throne because the new king said he did, and this was recognized by others, but surely would have gone away the minute he went against his "subject."

Pippin's successor in this title was his eldest son, Carl (Charles), better known as Charlemagne. Charlemagne ruled an empire in all but name, established in that form by his grandfather, Charles Martel, and worked to expand its borders and to solidify royal control over the various duchies. Part of how he did that was with an even closer alliance with the Church. To mark this, the Pope gave him a new title, one that at once exalted the Frankish ruler further but also made explicit the ties between the Empire and the Papacy.

The East-West schism came later, formally. But arguably, yes, this is part of that. The shift of power over the Pope out of Constantinople is an early stage of the whole mess of politics within the Mediterranean world and the church that would eventually get to where a dispute about the correct phrasing of the Nicene Creed would be enough to irreparably split the church.

This thread discussing the relationship between the HRE and ERE should be relevant. Some commenters mention that the Empress Irene, being a woman, wasn't accepted by Pope Leo III as legitimate.